LeetCode

LeetCode 143 Reorder List 풀이: 연결 리스트 분할·역순·병합

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

0. 문제 링크와 출처

첫 번째 노드부터 순서대로 가져오면서 마지막 노드를 번갈아 연결해야 하므로, 단순한 연결 리스트 순회만으로는 해결하기 어렵다. 중간 지점 찾기, 연결 리스트 뒤집기, 두 리스트 병합을 함께 구현하고 포인터 연결을 안전하게 관리해야 하므로 Level 3으로 판단했다.

1. 문제 요약

단일 연결 리스트가 다음과 같이 주어진다.

L0 -> L1 -> ... -> Ln-1 -> Ln

리스트를 다음 순서로 재배치해야 한다.

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

노드에 저장된 val 값은 변경할 수 없고, 노드 자체의 next 연결만 수정해야 한다. 노드 수는 1 이상 5 * 10^4 이하이며, 함수는 재배치된 리스트를 반환하지 않고 주어진 head에서 시작하는 연결을 직접 수정한다.

예를 들어 1 -> 2 -> 3 -> 4 -> 5는 1 -> 5 -> 2 -> 4 -> 3이 된다.

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

그래프 구조와 방문 기록

연결 리스트의 각 노드는 next로 다음 노드 하나만 가리키므로, 마지막 노드부터 접근하려면 뒤쪽 연결을 별도로 준비해야 한다. 배열에 모든 노드를 저장하지 않고 다음 세 단계로 연결 자체를 재배치한다.

  1. 느린 포인터와 빠른 포인터로 리스트의 중간을 찾고 두 부분으로 분리한다.
  2. 두 번째 부분의 next 방향을 뒤집는다.
  3. 첫 번째 부분과 뒤집힌 두 번째 부분을 한 노드씩 번갈아 연결한다.

fast를 head.next에서 시작하면 짝수 길이에서는 첫 번째 부분이 두 번째 부분보다 한 노드 길고, 홀수 길이에서는 가운데 노드가 첫 번째 부분에 남는다. 그래서 병합 중에는 두 번째 부분이 먼저 소진되고 첫 번째 부분의 남은 노드는 자연스럽게 마지막에 놓인다.

두 리스트를 교차 병합하는 순서

원래 후반부를 뒤에서부터 꺼내야 하지만 단일 연결 리스트에서는 뒤로 이동할 수 없다. 후반부를 역순으로 뒤집으면 후반부의 마지막 노드가 새로운 첫 노드가 되므로, 앞부분과 번갈아 병합하는 순서가 일반적인 앞에서 뒤로의 순회로 바뀐다.

각 연결을 수정하기 전에는 남은 노드로 이동할 next 포인터를 임시 변수에 저장해야 한다. 특히 병합 단계에서 first.next와 second.next를 먼저 저장하지 않으면 연결을 바꾸는 순간 아직 처리하지 않은 나머지 리스트에 접근할 수 없게 된다.

상태 전이와 경계 처리

중간을 찾은 뒤 slow.next를 None으로 바꿔 첫 번째 부분의 끝을 명확히 한다. 이 분리 작업을 생략하면 후반부를 뒤집는 과정에서 기존 연결이 남아 사이클이 만들어질 수 있다.

리스트 길이가 1이거나 head가 None인 경우에는 바꿀 연결이 없으므로 즉시 종료한다. 문제의 실제 입력은 한 개 이상의 노드를 보장하지만, 이 처리를 추가하면 함수가 빈 리스트에도 안전하게 동작한다.

오답 접근과 반례

매번 현재 리스트의 마지막 노드를 찾아 앞쪽에 연결하는 방식은 한 번의 삽입마다 남은 리스트를 순회해야 한다. 1 -> 2 -> 3 -> 4 -> 5에서 5, 4를 차례로 찾는 것처럼 노드가 많아질수록 전체 시간 복잡도가 O(n^2)이 되어 최대 5 * 10^4개 조건에 적합하지 않다.

모든 노드를 배열에 저장한 뒤 양끝 인덱스로 연결하는 방식은 시간 O(n)에 가능하지만 노드 수에 비례하는 O(n) 추가 공간을 사용한다. 이 글의 방식은 노드 연결만 바꾸어 추가 공간을 O(1)로 유지한다.

중간에서 두 리스트를 분리하지 않고 후반부를 뒤집으면 원래 앞부분의 연결과 뒤집힌 연결이 서로 이어질 수 있다. 그러면 병합 후 리스트가 끝나지 않거나 일부 노드가 반복되는 문제가 생기므로 slow.next = None이 필요하다.

시간·공간 복잡도

중간 찾기, 후반부 뒤집기, 두 리스트 병합은 각각 리스트를 한 번씩 순회한다. 그래서 전체 시간 복잡도는 O(n)이고, 몇 개의 포인터 변수만 사용하므로 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

class Solution:
    def reorderList(self, head: 'ListNode | None') -> None:
        if head is None or head.next is None:
            return

        # 첫 번째 부분의 마지막 노드를 찾는다.
        slow = head
        fast = head.next
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        # 두 번째 부분을 분리한다.
        second = slow.next
        slow.next = None

        # 두 번째 부분을 역순으로 뒤집는다.
        previous = None
        while second is not None:
            next_node = second.next
            second.next = previous
            previous = second
            second = next_node

        # 두 부분을 앞쪽 노드부터 번갈아 병합한다.
        first = head
        second = previous
        while second is not None:
            first_next = first.next
            second_next = second.next

            first.next = second
            second.next = first_next

            first = first_next
            second = second_next

함수의 반환 형식은 None이며, head가 가리키는 첫 노드는 그대로 유지된다. 병합할 때 두 번째 부분이 먼저 끝나므로 첫 번째 부분에 남은 가운데 노드는 별도의 처리를 하지 않아도 마지막에 연결되어 있다.

복사해 실행할 테스트

로컬 실행에서는 아래 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

head = make_list([1, 2, 3, 4])
Solution().reorderList(head)
assert to_list(head) == [1, 4, 2, 3]

4. 공식 예제와 추가 검증

연결 리스트를 직접 구성해 공식 예제와 길이가 다른 경계 케이스를 Python 코드로 실행했다. 각 결과에서 노드 값의 순서뿐 아니라 모든 원래 값이 한 번씩만 남는지도 확인했다.

공식 예제

입력 기대 출력 확인 결과
1 -> 2 -> 3 -> 4 1 -> 4 -> 2 -> 3 통과
1 -> 2 -> 3 -> 4 -> 5 1 -> 5 -> 2 -> 4 -> 3 통과

추가 검증 1: 한 노드

입력: 1
기대 출력: 1
확인 결과: 통과
검증 목적: 재배치할 연결이 없는 최소 리스트 확인

추가 검증 2: 두 노드

입력: 1 -> 2
기대 출력: 1 -> 2
확인 결과: 통과
검증 목적: 두 부분 중 두 번째 부분이 한 노드인 경계 확인

추가 검증 3: 홀수 길이 세 노드

입력: 1 -> 2 -> 3
기대 출력: 1 -> 3 -> 2
확인 결과: 통과
검증 목적: 가운데 노드가 첫 번째 부분에 남는지 확인

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

  • LeetCode 공식 문제는 노드 값을 바꾸지 않고 연결 리스트를 L0, Ln, L1, Ln-1 순서로 재배치하도록 정의한다.
  • NeetCode의 Reorder List 설명은 빠른·느린 포인터로 중간을 찾고, 두 번째 부분을 뒤집은 뒤 두 리스트를 교차 병합하는 접근을 설명한다.

모든 노드를 배열에 담으면 양끝 인덱스로 병합 순서를 만들기 쉽지만 O(n) 추가 공간이 필요하다. 재귀나 스택으로 뒤쪽 노드를 처리하는 방식도 가능하지만 호출 스택 또는 보조 자료구조가 필요하다. 이 글에서는 문제의 연결 리스트를 직접 수정하면서 O(1) 공간을 사용하는 세 단계 풀이를 선택했다.

마무리

Reorder List는 하나의 문제 안에서 연결 리스트의 대표적인 세 가지 조작을 함께 사용하는 문제다. 빠른·느린 포인터로 중간을 찾고, 후반부를 뒤집고, 두 부분을 번갈아 병합하면 노드 값을 바꾸지 않고도 원하는 순서를 만들 수 있다. 각 단계에서 다음 포인터를 잃지 않도록 임시로 저장하고 중간 연결을 끊는 것이 정확한 구현의 핵심이다.

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