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

"연결 리스트 뒤집기는 그 면접 질문이야. 어려워서가 아니라, 가짜로 못 해서: 포인터랑 그걸 다시 잇는 순서가 너한테 진짜인지, 그냥 단어인지를 시험해."

머릿속 그림

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) 공간 — 변수 셋으로 전체를 뒤집었어.

반복문 안 순서가 난이도 전부고, 첫 lesson 의 그 규칙이야: 덮어쓰려는 걸 덮어쓰기 전에 저장해. 옛 next 를 저장하기 전에 curr.next 를 뒤집으면 리스트 나머지가 허공으로 사라져.

뒤집으려면: 리스트를 걸으며 각 노드의 next-포인터를 뒤로 가리키게 뒤집어. 뒤집기 전에 다음 노드를 저장해, 안 그러면 리스트를 끊어. 반복은 세 포인터로 O(1) 공간; 재귀는 우아하지만 O(n) 스택 공간.

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

재귀는 몇 줄에 리스트를 뒤집을 수 있어: 나머지 리스트를 뒤집고, 다음 노드가 현재 노드를 되가리키게 해. 아름답게 읽혀 — 근데 모든 재귀 호출이 base case 가 반환할 때까지 콜 스택에 앉아서, O(n) 공간이 들고, 아주 긴 리스트에선 스택을 터뜨릴 수 있어 (RecursionError). 재귀 사고의 사랑스러운 시연이지만 (Recursion 트랙이 충분히 탐구해), production 에선 보통 반복 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 시작. 반복 1 후: nxt=2, 1.next=None, prev=1, curr=2. 계속 가. nxt 저장 전에 curr.next=prev 를 뒤집으면, 리스트 나머지로의 포인터를 잃어 — 뒤집기가 현재 노드 뒤 전부를 고립시켜.

머릿속 그림

반복 방식: 세 포인터

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

피파의 고백

Code

External links

Exercise

Progress

댓글 0