연결 리스트 Q2. 두 리스트를 번갈아 끼워 넣기

자료구조 C 실습 · 연결 리스트 · Q2

연결 리스트 Q2. 두 리스트를 번갈아 끼워 넣기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section A Linked List alternateMergeLinkedList

두 개의 연결 리스트가 주어질 때, 두 번째 리스트의 노드를 하나씩 떼어 첫 번째 리스트 사이사이에 번갈아 삽입하는 문제다. 새 노드를 만들지 않고 기존 노드의 `next`만 재배선한다는 점이 핵심이다. 결국 연결 리스트 문제는 '값 이동'이 아니라 '포인터 이동'이다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Linked_List\Q2_A_LL.c

대상 함수: alternateMergeLinkedList

카테고리: 연결 리스트

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Insert an integer to the linked list 1
• 2: Insert an integer to the linked list 2
• 3: Create the alternate merged linked list
• 0: Quit
• Input an integer that you want to add to the linked list 1
• Linked list 1

핵심 구현 흐름

STEP 1

두 리스트의 현재 노드와 다음 노드를 각각 백업한다.

STEP 2

첫 번째 리스트 현재 노드 뒤에 두 번째 리스트 노드를 연결한다.

STEP 3

삽입이 끝난 뒤 남은 두 번째 리스트의 시작점을 새 head로 갱신한다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: alternateMergeLinkedList

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
    ListNode *p1, *p2, *next1, *next2;  //1. 순회용 포인터 4개 선언
	int moved = 0;
	// 
    p1 = ll1->head;
    p2 = ll2->head;

	while (p1 != NULL && p2 != NULL)
		{
			next1 = p1 ->next;
			next2 = p2->next;     // 상태 백업용

			p1->next = p2;
			p2->next = next1; // 실제로 연결하는줄

			p1 = next1;   // 다음 단계 위해
        	p2 = next2;
        	moved++;

		}

		ll2->head = p2;				//ll2의 새로운 시작점을 p2로 바꿔라
    	ll1->size += moved;			//ll1 크기에, 이번에 ll2에서 가져온 노드 개수를 더해라
    	ll2->size -= moved;			//ll2 크기에서는, 빠져나간 노드 개수만큼 빼라


}

구현할 때 체크할 점

• 다음 노드를 백업하지 않으면 연결을 바꾸는 순간 나머지 리스트를 잃어버린다.
• 옮긴 노드 수만큼 두 리스트의 size를 같이 조정해야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 새 노드를 만들지 않고 기존 노드의 `next`만 재배선한다는 점이 핵심이다. 결국 연결 리스트 문제는 '값 이동'이 아니라 '포인터 이동'이다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.