LeetCode 206 - Reverse Linked List

단일 연결 리스트의 방향을 뒤집어 새로운 head를 반환하는 Easy 문제다. 노드를 새로 만들지 않고 기존 next 포인터를 반대로 연결했으며, 반복문 안에서 이전 노드와 현재 노드, 다음 노드를 순서대로 관리했다.

문제 링크 & 설명

문제 링크: 206. Reverse Linked List
요약: 단일 연결 리스트의 head가 주어졌을 때 모든 next 연결을 반대로 바꾸고, 뒤집힌 리스트의 head를 반환한다.

예를 들어 1 → 2 → 3 → None은 3 → 2 → 1 → None이 되어야 한다. 현재 노드의 next를 이전 노드로 바꾸는 순간 원래 다음 노드로 가는 연결이 사라지므로, 링크를 수정하기 전에 다음 노드를 별도로 보관해야 한다.

접근 방법

prev는 이미 방향을 뒤집은 구간의 head를 가리키고, current는 지금 처리할 노드를 가리킨다. 처음에는 뒤집힌 구간이 없으므로 prev를 None으로 시작한다.

prev = None
current = head

반복문에서는 먼저 current.next를 next_node에 저장한다. 그다음 현재 노드의 next를 prev로 바꾸고, 두 포인터를 한 칸씩 앞으로 이동한다.

next_node = current.next
current.next = prev
prev = current
current = next_node

첫 번째 노드의 next는 None으로 바뀌어 뒤집힌 리스트의 마지막 노드가 된다. current가 None에 도달하면 모든 링크를 처리한 상태이고, prev가 원래 리스트의 마지막 노드이자 새로운 head를 가리킨다.

복잡도 분석

시간 복잡도: O(n)
- 리스트의 각 노드를 정확히 한 번 방문한다.
공간 복잡도: O(1)
- 입력 크기와 관계없이 세 포인터만 사용하고 기존 노드의 링크를 직접 수정한다.

구현 코드

from typing import Optional

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        current = head

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        return prev

요약 및 회고

연결 리스트를 뒤집을 때 중요한 순서는 원래 다음 노드를 먼저 보관한 뒤 현재 링크를 수정하는 것이다. 이 순서를 바꾸면 아직 방문하지 않은 나머지 리스트로 가는 경로를 잃는다. 반복문이 끝난 뒤 current는 리스트 밖을 가리키고 prev가 새로운 head가 된다는 불변 조건까지 잡아두니 코드가 짧아도 각 포인터의 역할이 분명해졌다.