View in English →

Code › algorithm-study

LeetCode 21 - Merge Two Sorted Lists

dummy node와 포인터 이동으로 두 정렬 연결 리스트를 합친 Python 풀이

algorithmleetcodelinked-listtwo-pointersiterationdummy-nodepythonlearning

오름차순으로 정렬된 두 연결 리스트를 하나의 정렬된 리스트로 합치는 Easy 문제다. 두 리스트의 현재 노드만 비교하면서 더 작은 노드를 결과 리스트에 연결했고, 첫 노드를 따로 처리하지 않도록 dummy node를 사용했다.

문제 링크 & 설명

  • 문제 링크: 21. Merge Two Sorted Lists
  • 요약: 두 정렬 연결 리스트의 head가 주어졌을 때, 기존 노드들을 오름차순으로 연결한 리스트의 head를 반환하는 문제다.

두 리스트가 이미 정렬되어 있으므로 각 리스트의 앞쪽 노드만 비교하면 된다. 값이 더 작은 노드를 결과에 붙인 뒤 해당 리스트의 포인터를 다음 노드로 옮기면, 매 단계에서 아직 처리하지 않은 값 중 최솟값이 선택된다.

접근 방법

결과 리스트의 시작 지점을 만들기 위해 값 자체에는 의미가 없는 dummy node를 하나 생성했다. curr는 결과 리스트의 마지막 노드를 가리키며, 선택한 노드를 curr.next에 연결한 뒤 함께 앞으로 이동한다.

dummy = ListNode()
curr = dummy

두 리스트에 노드가 모두 남아 있는 동안 현재 값을 비교한다. list1의 값이 더 작으면 list1의 노드를 연결하고 list1을 다음으로 옮기며, 그렇지 않으면 list2에 같은 작업을 한다.

while list1 and list2:
    if list1.val < list2.val:
        curr.next = list1
        list1 = list1.next
    else:
        curr.next = list2
        list2 = list2.next
    curr = curr.next

반복문이 끝났다면 한쪽 리스트는 모두 소진된 상태다. 다른 리스트에 남은 노드들은 이미 정렬되어 있으므로 꼬리 전체를 그대로 연결하면 된다.

curr.next = list1 if list1 else list2

dummy는 구현을 위한 임시 시작점이므로 실제 결과의 head인 dummy.next를 반환한다.

트러블 슈팅

입력 중 하나가 처음부터 비어 있어도 별도 분기가 필요하지 않다. while 조건을 통과하지 않고 남은 리스트가 곧바로 curr.next에 연결되기 때문이다. 두 리스트가 모두 비어 있다면 curr.next에는 None이 연결되고, 반환값도 None이 된다.

dummy node를 결과에 포함하지 않는 것도 확인해야 한다. dummy는 첫 노드를 연결할 때 생기는 예외 처리를 없애기 위한 노드이므로 dummy가 아니라 dummy.next를 반환해야 한다.

복잡도 분석

  • 시간 복잡도: O(n + m)
    • 두 리스트의 각 노드를 최대 한 번씩 확인하고 연결한다.
  • 공간 복잡도: O(1)
    • 기존 노드의 next 포인터를 다시 연결하며, 입력 크기에 따라 늘어나는 별도 자료구조를 만들지 않는다.

구현 코드

from typing import Optional

class Solution:
    def mergeTwoLists(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy

        while list1 and list2:
            if list1.val < list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next

        curr.next = list1 if list1 else list2

        return dummy.next

요약 및 회고

정렬된 두 리스트에서는 현재 노드 중 작은 값을 선택하는 것만으로 전체 정렬 순서를 유지할 수 있다. dummy node를 두면 결과의 첫 노드를 연결하는 경우와 이후 노드를 연결하는 경우를 같은 코드로 처리할 수 있고, 한 리스트가 끝난 뒤에는 남은 꼬리를 한 번에 붙여 순회를 마칠 수 있다.