Ch.5 연결 리스트
Reverse Linked List — 3포인터의 마법
화살표 방향을 전부 뒤집어라!
1 → 2 → 3 → 4를 4 → 3 → 2 → 1로 바꿔야 합니다. 하지만 next를 바꾸는 순간 원래 다음 노드를 잃어버립니다. 이 문제를 해결하는 것이 3포인터 기법입니다.
포인터를 바꾸면서 원래 연결을 잃지 않으려면?
prev, curr, next 세 변수를 동시에 유지하면 안전하게 방향을 바꿀 수 있습니다.
핵심 내용
연결 방향을 바꾸려면 3개의 포인터가 필요합니다
3포인터 역할 prev: 이전 노드 (방향 바꿀 대상) curr: 현재 노드 nxt: 다음 노드 (미리 저장해서 잃어버리지 않기)
def reverse_list(head):
prev = None
curr = head
while curr:
nxt = curr.next # 다음 노드 저장
curr.next = prev # 방향 뒤집기
prev = curr # prev 전진
curr = nxt # curr 전진
return prev # 새로운 head4단계 반복: 저장(nxt) → 뒤집기(curr.next=prev) → 전진(prev, curr) — 시간 O(n), 공간 O(1)
재귀로도 뒤집을 수 있습니다. 끝까지 간 뒤 돌아오면서 방향을 바꿉니다
def reverse_list_recursive(head):
# Base case: 비어있거나 마지막 노드
if not head or not head.next:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head # 다음 노드가 나를 가리키게
head.next = None # 내 next 끊기
return new_head재귀는 직관적이지만 콜 스택 O(n) 공간을 사용합니다
Reverse 비교 Iterative: 시간 O(n), 공간 O(1) ← 면접 추천 Recursive: 시간 O(n), 공간 O(n) — 콜 스택
전체가 아닌 구간만 뒤집는 변형 문제도 자주 나옵니다
# LeetCode 92: Reverse Linked List II
def reverseBetween(head, left, right):
dummy = ListNode(0)
dummy.next = head
# left 이전 노드로 이동
prev = dummy
for _ in range(left - 1):
prev = prev.next
# 구간 reverse
curr = prev.next
for _ in range(right - left):
nxt = curr.next
curr.next = nxt.next
nxt.next = prev.next
prev.next = nxt
return dummy.next구간 Reverse는 dummy head + 3포인터의 조합. 전체 Reverse를 마스터하면 자연스럽게 풀립니다
Reverse 패턴은 k-Group Reverse, Palindrome 판별 등 다양한 문제로 확장됩니다
Reverse 패턴 변형 전체 뒤집기: prev/curr/nxt 3포인터 구간 뒤집기: dummy + left 이전 노드 + 반복 삽입 k개씩 뒤집기: 구간 뒤집기를 k개 단위로 반복 Palindrome: 절반 뒤집기 + 비교
reverse_list에서 while 루프가 끝났을 때 새로운 head는 어떤 변수인가?
iterative reverse의 공간 복잡도는?
3포인터 reverse에서 다음 노드를 미리 저장하는 변수: ___
재귀 reverse의 공간 복잡도는 O(1)이다
reverse에서 curr.next = prev를 실행하기 전에 반드시 해야 하는 것은?
3포인터 Reverse 마스터!
정리 노트
Reverse — 3포인터의 마법
Iterative 패턴
- 초기화
- prev = None, curr = head
- 루프 본문
- nxt 저장 → curr.next = prev → prev/curr 전진
- 반환
- prev (새로운 head)
복잡도
- Iterative
- 시간 O(n), 공간 O(1) ← 면접 추천
- Recursive
- 시간 O(n), 공간 O(n) — 콜 스택
Reverse Linked List는 연결 리스트 면접의 기본 중 기본. 눈 감고 쓸 수 있어야 한다!
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작