연결 리스트 Q7. 재귀로 리스트 뒤집기

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

연결 리스트 Q7. 재귀로 리스트 뒤집기

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

Section A Linked List RecursiveReverse

반복문 없이 재귀 호출만으로 단일 연결 리스트를 뒤집는 문제다. 재귀의 핵심은 맨 앞 노드를 직접 뒤집는 게 아니라, '나머지 리스트를 먼저 뒤집고 돌아오는 길에 현재 노드를 꼬리에 붙이는 것'이다.

한눈에 보는 문제 정보

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

대상 함수: RecursiveReverse

카테고리: 연결 리스트

문제에서 요구한 것

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

• 1: Insert an integer to the linked list
• 2: Reversed the linked list
• 0: Quit
• Input an integer that you want to add to the linked list
• The resulting linked list is
• The resulting linked list after reversed the given linked list is

핵심 구현 흐름

STEP 1

head와 나머지 리스트를 `firstNode`, `restOfList`로 나눈다.

STEP 2

나머지 리스트를 먼저 재귀적으로 뒤집는다.

STEP 3

돌아오면서 `firstNode->next->next = firstNode`로 방향을 뒤집고 마지막에 head를 갱신한다.

핵심 코드

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

핵심 코드: RecursiveReverse

void RecursiveReverse(ListNode **ptrHead)
{
	ListNode *firstNode, *restOfList;

	if (ptrHead == NULL || *ptrHead == NULL)
		return;

	firstNode = *ptrHead;
	restOfList = firstNode->next;

	if (restOfList == NULL)
		return;

	RecursiveReverse(&restOfList);
	firstNode->next->next = firstNode;
	firstNode->next = NULL;
	*ptrHead = restOfList;
}

구현할 때 체크할 점

• 기저 조건 없이 재귀를 타면 `next` 접근에서 바로 터진다.
• 뒤집은 뒤 `firstNode->next = NULL`을 하지 않으면 순환 리스트가 생긴다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 재귀의 핵심은 맨 앞 노드를 직접 뒤집는 게 아니라, '나머지 리스트를 먼저 뒤집고 돌아오는 길에 현재 노드를 꼬리에 붙이는 것'이다.

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