[Leetcode] 21. Merge Two Sorted Lists + 그림 풀이

문제: Merge Two Sorted Lists

• 관련 토픽: LinkedList, Recursion
• 난이도: Easy 
• 링크  https://leetcode.com/problems/merge-two-sorted-lists

요구사항

• list1, list2 LinkedList를 정렬된 하나의 LinkedList로 합치기 
• list1, list2는 정렬된 LinkedList 
• return 값의 list는 두 리스트를 기반으로 만든 값이어야 함 

조건

• LinkedList의 노드 길이는 [0, 50]
• -100 <= node.val <= 100 
• list1, list2는 오름차순 정렬 (non-decreasing) 

풀이

이미 정렬된 리스트들을 하나로 합치기 위해서는 brute-forcing, LinkedList, recursion을 사용할 수 도 있음 

여기에서는 LinkedList를 사용해서 풀이 

 

1. list1과 list2를 합치기 위해서, dummy linklist node를 하나 추가! list1과 list2의 앞에 node 하나를 덧붙인다는 생각. 

2. list1, list2를 함께 iterate 하면서 값을 비교하고 dummy node에 연결해 나아간다 

 

3. 현재 list1, list2가 각각 가리키는 값을 비교하고, 오름차순 정렬에 맞는 값으로 dummy의 next 포인터를 연결해 준다 

4. 길이가 다른 list의 경우에는, 먼저 list의 끝 (=None)을 마주하는 시점에 loop를 종료한다 

4-1. Loop가 종료된 시점에서 None을 가르키지 않는 list의 나머지 부분과 dummy node를 이어준다 

코드

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        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

        if list1 is not None: 
            current.next = list1
        else:
            current.next = list2

        return dummy.next

시간, 공간 복잡도 

시간 복잡도 O(n+m)

• 두 리스트를 병합하려면 각 리스트를 독립적으로 iterate 해야 함 
  • 동시에 같은 pointer가 가르키는 곳을 순회하는 것이 아닌, 조건 (list1.val < list2.val)에 부합하는 경우만 다음 val로 이동 
• list1의 길이가 n, list2의 길이가 m이라면 n + m의 반복이 발생
• W.C는 모든 노드를 하나씩 비교해 가면서 순회 -> n + m 의 반복

공간 복잡도 O(1)

• dummy, current와 같은 포인터 생성
• dummy = ListNode(0) 
• 둘다 상수 공간 복잡도에 해당 (이유: 입력크기 O(n+m)과 상관없이 항상 하나의 노드만 사용하기 때문)