C언어 연결 리스트 뒤집기 (Reverse Linked List)

핵심 정리

알고리즘 개요 심화

연결 리스트의 노드 순서를 거꾸로 바꾸는 알고리즘입니다. 새 노드를 만들지 않고 기존 노드 t1, t2, t3는 그대로 두고 각 노드 안의 next 값만 새로 덮어써서 화살표 방향을 거꾸로 바꿉니다. 값(5, 7, 11)을 서로 옮기지 않고도 화살표만 거꾸로 돌리면 결과가 같다는 점이 핵심입니다. 이를 in-place(제자리) 뒤집기라고 부릅니다.

핵심은 포인터 3개(prev, curr, next)를 한 노드씩 다음 노드로 이동시키며 curr->next를 prev 방향으로 다시 연결하는 것입니다.

연결 리스트 페이지에서 만든 t3 -> t2 -> t1 -> NULL 리스트를 뒤집어 t1 -> t2 -> t3 -> NULL로 만들어 봅시다.

코드 심화

prev는 NULL¹로 초기화합니다. while이 한 번 돌 때마다 1 ~ 4번이 차례로 실행됩니다. 그 후 다시 curr이 NULL인지 검사해서 NULL이면 빠져나옵니다.

루프가 끝났을 때 prev가 가리키고 있는 노드(&t1)가 새로운 시작점입니다. 원래 리스트의 마지막 노드 t1은 뒤집힌 리스트의 첫 노드가 됩니다. 마지막 회차에서 prev = curr = &t1이 실행된 후 루프가 끝나므로, 결과적으로 prev가 새 head를 가리키게 됩니다.

단계별 추적 심화

루프 진입 직전 상태

반복이 시작되기 전 변수와 노드의 상태입니다. prev는 NULL, curr은 시작 노드 &t3를 가리키고, 노드 연결은 아직 원래 방향(t3 -> t2 -> t1 -> NULL) 그대로입니다. 아래 다이어그램이 그 초기 상태입니다.

1회차 반복

curr = &t3인 상태에서 진입합니다.

1. next = curr->next → next = &t2
2. curr->next = prev → t3.next = NULL (원래 t3는 리스트의 첫 노드였지만, 뒤집은 결과 리스트에서는 마지막 노드가 됩니다. 그래서 t3.next를 NULL로 바꿔줍니다.)
3. prev = curr → prev = &t3
4. curr = next → curr = &t2

t3가 t2와 분리되고, prev가 t3로 이동합니다. 4번까지 실행한 뒤 다시 while 조건으로 돌아가 curr(=&t2)이 NULL인지 검사합니다. NULL이 아니므로 다시 1번부터 실행합니다.

2회차 반복

curr = &t2인 상태에서 진입합니다.

1. next = curr->next → next = &t1
2. curr->next = prev → t2.next = &t3 (t2 -> t3로 방향이 뒤집힘)
3. prev = curr → prev = &t2
4. curr = next → curr = &t1

t2가 t3 쪽으로 다시 연결되어 지금까지 뒤집힌 부분(t2 -> t3 -> NULL)이 만들어지고, 아직 안 뒤집힌 t1이 따로 남아 있습니다.

3회차 반복

curr = &t1인 상태에서 진입합니다.

1. next = curr->next → next = NULL
2. curr->next = prev → t1.next = &t2
3. prev = curr → prev = &t1
4. curr = next → curr = NULL

마지막 노드 t1이 t2 쪽으로 연결되며 전체 리스트가 완성됩니다. 다음 반복 조건 while(curr)은 curr이 NULL이므로 거짓이 되어 루프가 종료됩니다.

최종 결과

새 head = prev = &t1 → t1 -> t2 -> t3 -> NULL (값 순서: 5, 7, 11)

변수 변화 추적표 심화

각 회차 4단계가 모두 끝난 직후의 변수 상태입니다. next는 매 회차 1단계에서 갱신된 후 그 회차 동안 바뀌지 않으므로, 회차 후 next 값 = 그 회차 1단계 결과입니다.

여러 부분 리스트가 동시에 존재하면 |로 구분합니다. 화살표는 모두 next 방향(가리키는 쪽)을 의미합니다.

자주 하는 실수 심화

연습 문제