Merge Two Sorted Lists

문제 링크

• https://leetcode.com/problems/merge-two-sorted-lists/

문제 설명

두 개의 정렬된 연결 리스트 list1과 list2의 헤드가 주어질 때, 이 두 리스트를 하나의 정렬된 리스트로 병합하여 반환하는 함수를 작성하세요. 병합된 리스트는 첫 번째 두 리스트의 노드를 연결하여 만들어야 합니다.

• 출력: 병합된 정렬된 연결 리스트의 헤드

예제

• 예제 1
  • 입력: list1 = [1,2,4], list2 = [1,3,4]
  • 출력: [1,1,2,3,4,4]
• 예제 2
  • 입력: list1 = [], list2 = []
  • 출력: []
• 예제 3
  • 입력: list1 = [], list2 = [0]
  • 출력: [0]

풀이 전략

1. 두 포인터 사용: 각 리스트의 노드를 가리키는 두 개의 포인터를 설정합니다. 이를 통해 두 리스트를 동시에 탐색하면서 작은 값을 가진 노드를 병합된 리스트에 추가합니다.
2. 가상 헤드 사용: 병합된 리스트의 시작을 쉽게 관리하기 위해 더미 노드(dummy node)를 사용합니다. 이 노드는 병합된 리스트의 실제 헤드가 아니지만, 후속 작업에서 편리하게 사용할 수 있습니다.
3. 리스트 탐색 및 연결:
   • 두 리스트의 노드를 비교하여 작은 값을 가진 노드를 병합 리스트에 추가합니다.
   • 한 리스트가 끝날 때까지 이 과정을 반복합니다.
   • 한 리스트가 끝난 후, 다른 리스트의 남은 노드들을 병합 리스트에 추가합니다.

코드 분석

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 더미 노드 생성
        dummy = ListNode(0)
        tail = dummy  # tail은 현재 병합된 리스트의 마지막 노드를 가리킴

        # 두 리스트를 탐색하며 병합
        while list1 is not None and list2 is not None:
            if list1.val <= list2.val:
                tail.next = list1  # list1의 노드를 추가
                list1 = list1.next  # list1을 다음 노드로 이동
            else:
                tail.next = list2  # list2의 노드를 추가
                list2 = list2.next  # list2을 다음 노드로 이동

            tail = tail.next  # tail을 현재 추가한 노드로 이동

        # 남은 노드 추가
        if list1 is not None:
            tail.next = list1
        elif list2 is not None:
            tail.next = list2

        return dummy.next  # 더미 노드의 다음 노드가 병합된 리스트의 헤드

• 동작 원리:
  • dummy와 tail을 초기화합니다. dummy는 병합 리스트의 시작을 표시하고, tail은 현재 추가할 마지막 노드를 추적합니다.
  • while 루프를 통해 list1과 list2의 노드를 비교하며 작은 노드를 tail의 next에 추가합니다. 이 과정은 두 리스트 모두 비어있지 않을 때까지 반복됩니다.
  • 어느 한 리스트가 끝난 후, 다른 리스트의 남은 노드가 있을 경우, 그 노드를 tail.next에 연결합니다.
  • 마지막으로, 더미 노드의 next를 반환하여 병합된 리스트의 헤드를 반환합니다.
• 시간 복잡도: (O(n + m)) - 두 리스트의 모든 노드를 한 번씩 방문합니다. 여기서 (n)과 (m)은 각각 list1과 list2의 길이입니다.
• 공간 복잡도: (O(1)) - 추가 메모리를 사용하지 않으며, 단순히 노드의 포인터를 재조정합니다.

요약

• 두 개의 정렬된 연결 리스트를 병합하는 문제로, 투 포인터 방식을 사용하여 각 리스트를 동시에 탐색하면서 작은 값을 가진 노드를 병합 리스트에 추가합니다.
• 시간 복잡도 (O(n + m)), 공간 복잡도 (O(1))로 효율적인 해결 방법입니다.