WEEK 05 C언어 링크드 리스트 2,3,4번 문제(4월14일 월요일)

아침 중에 코어타임을 가지고, 배운 내용을 바탕으로 GCC에 대해 공부하여 미리 올려놨습니다.

오늘은 링크드 리스트 2, 3, 4번 문제를 C언어 기반으로 풀어보겠습니다.

2. C언어 Linked List 2번

[문제 내용]

2. alternateMergeLL

설명:

두 개의 연결 리스트가 주어졌을 때, 두 번째 리스트의 노드들을 첫 번째 리스트의 자리 사이사이에 삽입하는 함수 작성.

※ 첫 번째 리스트의 자리가 부족하면, 두 번째 리스트의 남은 노드는 그대로 유지됨

함수 원형:

void alternateMergeLL(LinkedList *ll1, LinkedList *ll2);

예시:

• 리스트1: 1, 2, 3 리스트2: 4, 5, 6, 7 → 결과: 리스트1: 1, 4, 2, 5, 3, 6, 리스트2: 7
  
• 리스트1: 1, 5, 7, 3, 9, 11 리스트2: 6, 10, 2, 4 → 결과: 리스트1: 1, 6, 5, 10, 7, 2, 3, 4, 9, 11, 리스트2: (비어 있음)
  

[풀이 방법]

1. 두개의 연결 리스트를 받을 수 있어야한다.
2. 리스트1의 각각의 수 사이에 리스트2의 수가 번갈아서 추가되야한다.(인덱스 재조정)
3. 만약, 리스트2가 남는다면 남은 리스트2의 값을 출력한다.
4. 결과로 리스트1과 리스트2를 출력한다.

[코드와 해설]

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
    /*
	1. 두개의 연결 리스트를 받을 수 있어야한다.
	2. 리스트1의 각각의 수 사이에 리스트2의 수가 번갈아서 추가되야한다.(인덱스 재조정)
	3. 만약, 리스트2가 남는다면 남은 리스트2의 값을 출력한다.
	4. 결과로 리스트1과 리스트2를 출력한다.
	*/

	ListNode * L1 = ll1 -> head;  // L1을 리스트1으로 받음
	ListNode * L2 = ll2 -> head;  // L2을 리스트2으로 받음

	if(ll1 == NULL || ll2 == NULL){   // 리스트에 아무 것도 없을 떄의 예외처리
		return;
	}
	
	int index = 1; // 리스트 1에 끼워 넣을 위치 (처음은 1부터 시작)
	ListNode *temp; // L2에서 사용할 임시 포인터

	while (L1 != NULL && L2 != NULL) {
		// L2의 현재 값을 L1에 끼워 넣기
		insertNode(ll1, index, L2->item);

		// 다음 L1위치로 건너 뜀.(방금 삽입된 노드 다음부터 시작)
		L1 = findNode(ll1, index + 1);

		// temp로  L2 현재 노드 저장 후 다음 노드로 이동
		temp = L2;
		L2 = L2->next;

		// 끼워넣은 노드는 ll2에서 제거(free처리) 메모리 누수 방지
		free(temp);
		ll2->size--;

		// 다음 삽입 인덱스는 두 칸 뒤
		index += 2;
	}

	// 리스트2 헤드 갱신
	ll2->head = L2;

}

3. C언어 Linked List 3번

[문제 내용]

3. moveOddItemsToBackLL

설명:

연결 리스트에서 홀수 값을 모두 뒤쪽으로 이동시키는 함수 작성

함수 원형:

void moveOddItemsToBackLL(LinkedList *ll);

예시:

• 입력: 2, 3, 4, 7, 15, 18 결과: 2, 4, 18, 3, 7, 15
  

[풀이 방법]

입력된 리스트에서 홀수 값을 모두 리스트 맨뒤로 보내야한다.
1. 입력 받은 리스트에서 2로 나누었을때 나머지가 존재함을 확인해 홀수임을 판단.
2. 순회하면서 홀수에 해당되면 해당 수 제거후 맨뒤 NULL인 부분에 재연결.
3. 사이즈는 동일하고 맨뒤 head와 NULL처리 잘 해줘야한다.

[코드와 해설]

void moveOddItemsToBack(LinkedList *ll)
{
	/* 
	입력된 리스트에서 홀수 값을 모두 리스트 맨뒤로 보내야한다.
	1. 입력 받은 리스트에서 2로 나누었을때 나머지가 존재함을 확인해 홀수임을 판단.
	2. 순회하면서 홀수에 해당되면 해당 수 제거후 맨뒤 NULL인 부분에 재연결.
	3. 사이즈는 동일하고 맨뒤 head와 NULL처리 잘 해줘야한다.
	*/
	if(ll == NULL || ll->head == NULL){  // 예외처리
		return;
	}

	int index = 0;   // 현재 검사 중인 인덱스
	int count = 0;  // 반복 횟수 지정자
	int size = ll->size;  // 원래 크기 저장

	// 리스트 처음부터 끝까지 순회(무한 루프 방지와 범위 검사를 수행)
	while (count < size && index < size) {
		ListNode *node = findNode(ll, index);   // 현재 index에 해당하는 노드를 가져온다

		if (node == NULL) break;  // 안정성 확보: 노드가 NULL이면 종료
		
		if(node->item % 2 != 0){     // 나머지가 0이 아니면,즉 홀수이면 처리
		int value = node->item;    // 값을 따로 저장해둠 (삭제하면 사라지기 때문)
		removeNode(ll, index);    // 해당 인덱스 제거
		insertNode(ll, ll->size, value);   // 맨뒤 다시 추가, 사이즈 이미 줄였어서 그 자리가 끝이다.
	
	// 삭제했기 때문에 같은 index에서 다시 검사(index 유지)
	} 
	else {
		index++;   // 짝수면 다음 index로 넘어감
	}   
	count++;   // 반복 횟수 증가
    }
}

4. C언어 Linked List 4번

[문제 내용]

4. moveEvenItemsToBackLL

설명:

연결 리스트에서 짝수 값을 모두 뒤쪽으로 이동시키는 함수 작성

함수 원형:

void moveEvenItemsToBackLL(LinkedList *ll);

예시:

• 입력: 2, 3, 4, 7, 15, 18 결과: 3, 7, 15, 2, 4, 18
  

[풀이 방법]

입력된 리스트에서 짝수 값을 모두 리스트 맨뒤로 보내야한다.
1. 리스트 자체가 NULL인 경우를 예외처리로 리턴.
2. 리스트 순회하면서 짝수이면 값을 따로 저장한 다음 제거하고 맨뒤에 추가한다.
3. 다음 인덱스로 넘어가면서 체크, count를 따로 둬서 무한 루프 방지

[코드와 해설]

void moveEvenItemsToBack(LinkedList *ll)
{
	/*
	입력된 리스트에서 짝수 값을 모두 리스트 맨뒤로 보내야한다.
	1. 리스트 자체가 NULL인 경우를 예외처리로 리턴.
	2. 리스트 순회하면서 짝수이면 값을 따로 저장한 다음 제거하고 맨뒤에 추가한다.
	3. 다음 인덱스로 넘어가면서 체크, count를 따로 둬서 무한 루프 방지
	*/
	if(ll == NULL || ll->head == NULL){  // 예외처리
		return;
	}

	int index = 0;   // 현재 검사 중인 인덱스
	int count = 0;  // 반복 횟수 지정자
	int size = ll->size;  // 원래 크기 저장

	// 리스트 처음부터 끝까지 순회(무한 루프 방지와 범위 검사를 수행)
	while (count < size && index < size) {
		ListNode *node = findNode(ll, index);   // 현재 index에 해당하는 노드를 가져온다

		if (node == NULL) break;  // 안정성 확보: 노드가 NULL이면 종료
		
		if(node->item % 2 == 0){     // 나머지가 0이면,즉 짝수이면 처리
		int value = node->item;    // 값을 따로 저장해둠 (삭제하면 사라지기 때문)
		removeNode(ll, index);    // 해당 인덱스 제거
		insertNode(ll, ll->size, value);   // 맨뒤 다시 추가, 사이즈 이미 줄였어서 그 자리가 끝이다.
	
	// 삭제했기 때문에 같은 index에서 다시 검사(index 유지)
	} 
	else {
		index++;   // 짝수면 다음 index로 넘어감
	}   
	count++;   // 반복 횟수 증가
    }
} 

위의 내용을 끝내고 내일 퀴즈에 나오는 문제인 BST와 B-Tree를 공부했습니다.
BST는 팀원분이 내일 아침에 정리해서 알려주시기로 했고, B-Tree를 중점적으로 공부하였습니다. 해당 공부에 관련된 내용은 미리 포스팅 해놓았습니다. 2가지 형태를 원하시는 스타일대로 공부하시면 좋을 것 같습니다.