LeetCode

LeetCode 206 Reverse Linked List 풀이: 포인터 방향을 뒤집는 반복문

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

현재 노드의 next 방향을 이전 노드로 바꾸면서도 아직 방문하지 않은 다음 노드를 잃지 않아야 한다. 포인터 세 개의 역할과 갱신 순서를 정확히 관리해야 하지만 별도의 복잡한 자료구조는 필요하지 않으므로 Level 2로 판단했다.

1. 문제 요약

단일 연결 리스트의 시작 노드 head가 주어질 때, 리스트의 방향을 반대로 뒤집은 뒤 새로운 시작 노드를 반환한다. 기존 노드를 새로 복사하지 않고 next 연결을 직접 수정한다.

중요한 조건은 다음과 같다.

  • 노드 수는 0 이상 5000 이하이다.
  • 노드 값은 -5000 이상 5000 이하이다.
  • 빈 리스트가 입력될 수 있다.
  • 결과는 기존 연결 리스트의 노드 연결을 반대로 바꾼 리스트다.

예를 들어 1 -> 2 -> 3 -> 4 -> 5를 뒤집으면 5 -> 4 -> 3 -> 2 -> 1이 된다. 빈 리스트는 뒤집어도 빈 리스트이므로 None을 그대로 반환한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

연결 리스트 포인터 상태

반복문에서 세 가지 포인터를 사용한다.

  • previous: 현재 노드의 뒤에 연결할 이미 뒤집힌 리스트의 시작점
  • current: 아직 방향을 바꾸지 않은 현재 노드
  • next_node: current.next를 방향 변경 전에 저장한 다음 노드
현재 노드의 다음 노드를 저장한 뒤 연결 방향을 뒤집고 포인터를 이동하는 과정
다음 노드를 먼저 저장하고 현재 노드의 연결 방향을 반대로 바꾼다.

초기 상태는 previous = None, current = head다. 한 번의 반복에서 다음 순서로 처리한다.

  1. current.next를 next_node에 저장한다.
  2. current.next = previous로 현재 노드의 방향을 뒤집는다.
  3. previous = current로 뒤집힌 리스트의 시작점을 갱신한다.
  4. current = next_node로 아직 처리하지 않은 다음 노드로 이동한다.

반복이 끝나면 current는 None이고, previous가 새 head다.

링크를 바꾸기 전에 다음 노드를 보존하기

연결 리스트는 배열처럼 이전 원소를 인덱스로 찾을 수 없다. 현재 노드의 next를 바로 덮어쓰면 원래 다음 노드로 갈 수 있는 유일한 연결을 잃게 된다.

그래서 방향을 바꾸기 전에 반드시 원래 다음 노드를 저장해야 한다.

저장 전: previous <- current -> next_node -> ...
방향 변경: previous <- current <- next_node? 가 아니라,
           previous <- current    next_node -> ...

실제 한 단계의 상태는 다음과 같다.

이전: None <- 1    2 -> 3 -> None
처리: None <- 1 <- 2    3 -> None
처리: None <- 1 <- 2 <- 3

상태 전이와 경계 처리

빈 리스트이면 current가 처음부터 None이므로 반복문이 실행되지 않고 previous, 즉 None을 반환한다. 노드가 하나뿐이면 그 노드의 next를 None으로 설정한 뒤 그 노드를 반환하므로 별도 분기가 필요하지 않다.

마지막 노드를 처리할 때 next_node는 None이 된다. 마지막 노드의 next를 이전 노드로 연결하고 current를 None으로 이동하면 반복이 끝나며, 마지막으로 처리한 노드가 새 head가 된다.

시간·공간 복잡도

각 노드를 한 번씩 방문하고 next 연결을 한 번씩 바꾸므로 시간 복잡도는 O(n)이다. 포인터 몇 개만 저장하고 새로운 배열이나 노드 목록을 만들지 않으므로 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

current.next를 수정하기 전에 next_node에 원래 연결을 저장한다. 방향을 바꾼 뒤 두 포인터를 한 칸씩 이동하고, 모든 노드를 처리하면 previous를 반환한다.

class Solution:
    def reverseList(self, head: 'ListNode | None') -> 'ListNode | None':
        previous = None
        current = head

        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node

        return previous

가장 중요한 순서는 next_node 저장, current.next 변경, 포인터 이동이다. previous는 이미 방향을 뒤집은 리스트의 head이고, 마지막 반복이 끝나면 전체 역순 리스트의 head가 된다.

4. 오답 접근과 반례

다음 노드를 저장하지 않고 연결을 바꾸기

다음과 같이 current.next를 먼저 바꾸면 원래 다음 노드로 이동할 방법을 잃는다.

current.next = previous
current = current.next  # 원래 다음 노드가 아니라 previous로 이동

1 -> 2 -> 3에서 첫 노드의 next를 None으로 바꾼 뒤 current = current.next를 실행하면 리스트의 나머지 2 -> 3에 도달할 수 없다. 반드시 수정 전의 current.next를 임시 변수에 저장해야 한다.

노드 값만 역순으로 복사하기

값을 배열에 모아 역순으로 반환하면 값의 순서는 만들 수 있지만, 문제에서 요구하는 연결 리스트의 next 구조를 직접 뒤집는 방식이 아니다. O(n) 추가 공간도 필요하다.

head를 그대로 반환하기

연결만 뒤집고 원래 head를 반환하면 새 리스트의 시작점이 잘못된다.

원래: 1 -> 2 -> 3 -> None
뒤집은 연결: None <- 1 <- 2 <- 3
새 head: 3

원래 head인 1은 역순 리스트의 마지막 노드가 되므로, 마지막으로 처리한 previous를 반환해야 한다.

복사해 실행할 테스트

로컬 실행에서는 아래 ListNode와 헬퍼를 풀이 클래스 앞에 두고, 검증 코드를 클래스 뒤에 붙여 실행한다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def make_list(values):
    dummy = tail = ListNode()
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next

def to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result

assert to_list(Solution().reverseList(make_list([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert Solution().reverseList(None) is None

5. 공식 예제와 추가 검증

작성한 reverseList 함수를 Python에서 직접 연결 리스트 노드로 구성해 공식 예제와 빈 리스트, 단일 노드, 중복 값 케이스를 확인했다.

공식 예제

입력: head = [1,2,3,4,5]
기대 출력: [5,4,3,2,1]
확인 결과: 통과
입력: head = [1,2]
기대 출력: [2,1]
확인 결과: 통과
입력: head = []
기대 출력: []
확인 결과: 통과

추가 검증 1: 단일 노드

입력: head = [7]
기대 출력: [7]
확인 결과: 통과
검증 목적: 노드 하나의 next가 None으로 유지되는지 확인

추가 검증 2: 음수와 중복 값

입력: head = [-3,0,0,8]
기대 출력: [8,0,0,-3]
확인 결과: 통과
검증 목적: 값의 크기나 중복 여부와 관계없이 연결 순서만 뒤집는지 확인

추가 검증 3: 결과가 원본 노드를 재사용하는지 확인

입력: head = [1,2,3]
검증: 반환 리스트의 노드 id 집합과 입력 리스트의 노드 id 집합 비교
기대 결과: 같은 노드들을 역순으로 연결
확인 결과: 통과
검증 목적: 새 노드를 만들지 않고 next 연결만 수정하는지 확인

6. 다른 풀이 방식 검색 및 비교

재귀형 풀이는 현재 노드의 다음 리스트를 먼저 뒤집은 뒤 다음 노드의 next를 현재 노드로 연결하는 방식이다. 이해하기 쉽지만 재귀 호출 스택에 O(n) 공간을 사용한다.

이 글의 반복형 풀이는 previous, current, next_node만 유지하므로 O(1) 추가 공간으로 처리한다. 두 방식 모두 각 노드를 한 번씩 방문해 시간 복잡도는 O(n)이다.

마무리

Reverse Linked List의 핵심은 현재 노드의 연결을 바꾸기 전에 원래 다음 노드를 저장하는 것이다. previous와 current를 한 칸씩 이동하며 current.next를 이전 노드로 바꾸면 새 head를 잃지 않고 전체 리스트를 뒤집을 수 있다. 반복형 구현은 O(n) 시간과 O(1) 공간으로 동작한다.

관련 문제

#연결 리스트#LeetCode#난이도 2