LeetCode

LeetCode 21 Merge Two Sorted Lists 풀이: 더미 노드와 두 포인터 병합

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

0. 문제 링크와 출처

두 연결 리스트의 정렬 상태를 유지하면서 노드의 next 연결을 직접 재배치해야 한다. 더미 노드와 두 포인터를 사용하면 구현은 간단하지만, 포인터를 잃지 않고 남은 리스트까지 연결해야 하므로 연결 리스트 조작에 대한 이해가 필요해 Level 3으로 판단했다.

1. 문제 요약

오름차순으로 정렬된 두 단일 연결 리스트 list1, list2가 주어진다. 두 리스트의 노드를 새로 복사하지 않고 next 연결을 이어 붙여 하나의 정렬된 연결 리스트로 만들고, 병합된 리스트의 시작 노드를 반환해야 한다.

두 리스트는 비내림차순으로 정렬되어 있으며, 전체 노드 수는 최대 50개다. 값이 같은 노드도 있을 수 있으므로 두 리스트의 현재 값이 같을 때도 하나를 선택해 계속 진행해야 한다.

예를 들어 다음 두 리스트를 병합하면 된다.

list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4

결과: 1 -> 1 -> 2 -> 3 -> 4 -> 4

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

그래프 구조와 방문 기록

각 리스트의 현재 노드를 가리키는 list1, list2와 결과 리스트의 마지막 노드를 가리키는 current를 사용한다. 실제 결과의 시작 노드를 매번 특별하게 처리하지 않도록 값이 무관한 더미 노드를 하나 만들고, dummy.next를 최종 결과의 시작점으로 사용한다.

두 현재 노드 중 더 작은 값을 가진 노드를 결과 뒤에 연결한다. 선택한 리스트의 포인터만 다음 노드로 이동하고, 결과의 끝 포인터는 방금 연결한 노드로 이동한다.

작은 head부터 연결해도 정렬이 유지되는 이유

두 리스트가 이미 정렬되어 있으므로 현재 두 노드 중 작은 노드는 전체 병합 결과의 다음 노드가 될 수밖에 없다. 선택하지 않은 리스트의 뒤쪽 노드가 현재 선택된 노드보다 앞에 올 수 없기 때문이다.

한 리스트가 먼저 끝나면 다른 리스트의 남은 부분은 이미 정렬되어 있고, 앞서 병합한 마지막 노드보다 작아질 수 없다. 그래서 남은 리스트 전체를 current.next에 한 번에 연결할 수 있다.

상태 전이와 경계 처리

반복 조건은 두 리스트가 모두 남아 있는 동안이다.

  1. list1.val과 list2.val을 비교한다.
  2. 더 작은 노드를 current.next에 연결한다. 값이 같으면 list1을 먼저 선택한다.
  3. 선택한 리스트의 포인터를 다음 노드로 이동한다.
  4. current를 방금 연결한 노드로 이동한다.

반복이 끝나면 둘 중 하나는 None이다. list1이 남아 있으면 그것을, 그렇지 않으면 list2를 그대로 연결한다. 두 입력 리스트가 모두 비어 있으면 dummy.next도 None이므로 빈 리스트를 그대로 반환한다.

오답 접근과 반례

두 리스트의 값을 모두 배열에 복사하고 다시 정렬하면 결과는 만들 수 있지만, 이미 정렬된 입력의 장점을 사용하지 못하고 O((n + m) log(n + m)) 시간이 필요하다. 이 문제는 두 포인터로 한 번씩만 비교하면 O(n + m)에 해결할 수 있다.

비교 루프가 끝난 뒤 남은 리스트를 연결하지 않으면 한쪽이 더 긴 입력에서 노드가 잘린다.

list1: 1 -> 2 -> 3
list2: 4

4를 연결하지 않으면 결과가 1 -> 2 -> 3에서 끝나므로, 반복문 이후 남은 리스트를 반드시 연결해야 한다.

더미 노드 없이 첫 노드를 직접 정하면 첫 삽입만 별도 조건으로 처리해야 한다. 이 분기를 놓치면 첫 번째 노드가 유실되거나 결과 시작 포인터가 잘못될 수 있으므로 더미 노드로 모든 삽입을 같은 형태로 처리한다.

시간·공간 복잡도

각 노드는 병합 과정에서 한 번만 선택되므로 시간 복잡도는 O(n + m)이다. 새 노드를 만들지 않고 입력 노드의 연결만 바꾸며 포인터 몇 개만 사용하므로 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

class Solution:
    def mergeTwoLists(
        self,
        list1: 'ListNode | None',
        list2: 'ListNode | None',
    ) -> 'ListNode | None':
        dummy = ListNode()
        current = dummy

        while list1 is not None and list2 is not None:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next

            current = current.next

        current.next = list1 if list1 is not None else list2
        return dummy.next

dummy 자체는 결과에 포함하지 않는 임시 노드다. current는 항상 결과 리스트의 마지막 노드를 가리키고, 최종적으로 dummy.next만 반환한다.

값이 같을 때 list1을 먼저 선택하도록 <=를 사용했다. 어느 노드를 먼저 선택해도 값의 정렬은 유지되지만, 같은 값에서 일관된 연결 순서를 만들 수 있다.

복사해 실행할 테스트

로컬 실행에서는 아래 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().mergeTwoLists(make_list([1, 2, 4]), make_list([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
assert Solution().mergeTwoLists(None, None) is None

4. 공식 예제와 추가 검증

연결 리스트 노드를 직접 구성해 공식 예제와 빈 리스트, 음수·중복 값, 길이가 다른 리스트를 Python 코드로 실행했다. 결과 값뿐 아니라 입력 노드가 그대로 재사용되었는지도 확인했다.

공식 예제

입력: list1 = [1, 2, 4], list2 = [1, 3, 4]
기대 출력: [1, 1, 2, 3, 4, 4]
확인 결과: 통과
검증 목적: 두 정렬 리스트의 일반적인 병합 확인

추가 검증 1: 두 리스트가 모두 빈 경우

입력: list1 = [], list2 = []
기대 출력: []
확인 결과: 통과
검증 목적: 두 시작 포인터가 모두 None인 경계 확인

추가 검증 2: 한 리스트만 남는 경우

입력: list1 = [], list2 = [0]
기대 출력: [0]
확인 결과: 통과
검증 목적: 반복문에 진입하지 않고 남은 리스트를 연결하는지 확인

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

입력: list1 = [-10, -3, 7], list2 = [-8, -3, 2, 9]
기대 출력: [-10, -8, -3, -3, 2, 7, 9]
확인 결과: 통과
검증 목적: 음수와 동일한 값이 섞인 비내림차순 병합 확인

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

재귀형 풀이도 매 단계에서 더 작은 노드를 선택하고 나머지 리스트를 재귀적으로 병합하므로 시간 복잡도는 O(n + m)이다. 다만 노드 수만큼 호출 스택이 필요해 공간 복잡도가 O(n + m)이 될 수 있다. 이 글에서는 반복형 풀이를 사용해 입력 노드와 포인터 외의 추가 공간을 O(1)로 유지했다.

마무리

Merge Two Sorted Lists는 정렬된 두 자료구조를 하나로 합치는 기본적인 투 포인터 문제다. 현재 두 노드 중 작은 노드를 선택하고, 한 리스트가 끝나면 남은 리스트를 그대로 연결하면 된다. 더미 노드를 사용하면 결과의 첫 노드를 따로 처리하지 않아도 되어 연결 변경의 경계 오류를 줄일 수 있다.

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