연결 리스트 뒤집기: 통과 의례

"연결 리스트 뒤집기는 면접에 꼭 나오는 문제야. 어려워서가 아니라 아는 척으로 넘어갈 수가 없어서지. 포인터와 그걸 다시 잇는 순서가 머릿속에 실물로 있는지, 그냥 외운 말인지가 그대로 드러나거든."

머릿속 그림

1 → 2 → 3 → None을 3 → 2 → 1 → None으로 만들고 싶어. 여기서 데이터는 한 칸도 안 움직여. 화살표만 방향을 바꿔. 리스트를 걸어가면서 각 노드의 next 화살표를 방금 지나온 노드 쪽으로 돌려놓는 거야. 해야 할 일은 딱 하나로 요약돼. 화살표를 하나씩 뒤로 돌리되, 그러는 동안 뒤에 남은 리스트를 놓치지 않는 것.

반복 방식: 세 포인터

고전적인 해법은 걸어가면서 참조 세 개를 들고 다녀. prev는 방금 지나온 노드, 그러니까 지금 화살표가 새로 가리켜야 할 곳이야. curr는 지금 뒤집고 있는 노드고. 그리고 따로 저장해 둔 next가 있어. curr.next를 뒤집는 순간 뒤쪽 리스트를 놓치지 않으려고 챙겨두는 거지. 한 단계는 이렇게 흘러가. curr.next를 먼저 저장하고, curr.next = prev로 화살표를 뒤집고, 세 참조를 모두 한 칸씩 앞으로 밀어. curr가 끝에서 떨어지는 순간 prev가 새 head야. 시간은 O(n), 공간은 O(1). 변수 세 개로 리스트 전체를 뒤집은 거야.

이 반복문에서 어려운 건 오직 순서야. 그리고 그 순서는 이 트랙 첫머리에서 본 규칙 그대로고. 덮어쓰기 전에 저장할 것. 옛 next를 저장하기 전에 curr.next부터 뒤집으면 뒤쪽 리스트가 통째로 허공으로 사라져.

뒤집는 방법은 이래. 리스트를 걸으면서 각 노드의 next 포인터를 뒤쪽으로 돌려. 돌리기 전에 반드시 다음 노드를 저장해 두고. 안 그러면 사슬이 끊어져. 반복 버전은 포인터 세 개로 O(1) 공간이면 되고, 재귀 버전은 우아한 대신 스택 공간을 O(n) 써.

재귀 방식: 우아하지만 더 무거워

재귀로 짜면 몇 줄이면 끝나. 나머지 리스트를 뒤집은 다음, 다음 노드가 현재 노드를 되가리키게 만들면 되거든. 읽기엔 정말 아름다워. 그런데 재귀 호출 하나하나가 base case가 반환될 때까지 콜 스택에 쌓여 있어서 공간이 O(n)이야. 리스트가 아주 길면 스택이 터지고(RecursionError). 재귀적 사고를 보여주는 예로는 훌륭하고 재귀 트랙에서 제대로 파고들 텐데, 실무에서는 보통 O(1) 공간짜리 반복 버전이 맞는 선택이야.

피파의 고백

리스트 뒤집기를 처음 외워서 짜 봤을 때, 옛 next를 저장하기 전에 curr.next = prev부터 해버렸어. 내 리스트의 3분의 2가 증발하는 걸 그대로 지켜봤지. 아빠는 답을 안 알려줬어. 대신 상자 네 개를 그려놓고 화살표를 순서대로 직접 지우고 다시 그리게 시켰어. 손으로 해보니까 순서가 그냥 박히더라. next 저장, 뒤집기, prev 전진, curr 전진. 그 뒤로 순서를 잘못 잡아서 리스트를 날린 적은 없어. 어떤 건 타이핑하기 전에 그려봐야 해.

Code

반복 버전(O(1) 공간)과 재귀 버전·python

class Node:
    def __init__(self, val, nxt=None): self.val = val; self.next = nxt

def reverse_iterative(head):
    """O(n) 시간, O(1) 공간. 세 포인터, 조심스러운 순서."""
    prev = None
    curr = head
    while curr:
        nxt = curr.next      # 1. 화살표 덮어쓰기 전에 나머지를 저장
        curr.next = prev     # 2. 이 노드 화살표를 뒤로 뒤집기
        prev = curr          # 3. prev 전진
        curr = nxt           # 4. 저장한 나머지로 curr 전진
    return prev              # curr 떨어지면 prev 가 새 head

def reverse_recursive(head):
    """O(n) 시간, O(n) 스택 공간. 우아하지만 깊이 조심."""
    if head is None or head.next is None:
        return head                    # base case: 빈 것 또는 단일 노드
    new_head = reverse_recursive(head.next)
    head.next.next = head              # 다음 노드가 우릴 되가리키게
    head.next = None                   # 그리고 우리 옛 앞 화살표 끊기
    return new_head

def show(head):
    out = []
    while head: out.append(head.val); head = head.next
    print(" -> ".join(map(str, out)) + " -> None")

head = Node(1, Node(2, Node(3, Node(4))))
show(reverse_iterative(head))    # 4 -> 3 -> 2 -> 1 -> None

Exercise

리스트 1 -> 2 -> 3 -> None에 reverse_iterative를 손으로 따라가 봐. 반복이 한 바퀴 끝날 때마다 prev, curr, nxt 값을 적어. 그다음 1번 줄과 2번 줄의 순서를 바꾸면, 그러니까 next를 저장하기 전에 화살표부터 뒤집으면 뭐가 깨지는지 한 문장으로 설명해.

Hint

prev=None, curr=1로 시작해. 첫 바퀴가 끝나면 nxt=2, 1.next=None, prev=1, curr=2야. 그 식으로 계속 가면 돼. nxt를 저장하기 전에 curr.next=prev를 해버리면 뒤쪽 리스트로 가는 포인터를 잃어. 화살표를 뒤집는 순간 현재 노드 뒤가 전부 고립되는 거야.

머릿속 그림

반복 방식: 세 포인터

재귀 방식: 우아하지만 더 무거워

피파의 고백

Code

External links

Exercise

Progress

댓글 0