[Leetcode/파이썬] 23. Merge K Sorted Lists

Merge k Sorted Lists

---

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted linked list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0 :
            return None

        # Merge Multi to Single Linked List
        dummy = ListNode(-10001)
        curr = dummy

        # Merge
        for head in lists :
            curr.next = head
            # Move Pointer 
            while curr and curr.next :
                curr = curr.next
        
        # Pruning
        if dummy.next is None or dummy.next.next is None :
            return dummy.next
        
        # Divde
        return self.divide(dummy.next)

    def divide(self, head) :
        # Return condition
        if head is None or head.next is None :
            return head
        
        # Find mid
        slow, fast = head, head.next

        while fast and fast.next :
            slow = slow.next
            fast = fast.next.next

        mid = slow.next
        slow.next = None

        # Divided Single node
        left = self.divide(head)
        right = self.divide(mid)

        # Merge
        return self.merge(left, right)

    def merge(self, left, right) :
        res = ListNode(-10001)
        curr = res

        # Merge
        while left and right :
            if left.val < right.val :
                curr.next = left
                left = left.next
            else :
                curr.next = right
                right = right.next

            curr = curr.next

        curr.next = left or right

        return res.next

이 문제는 Leetcode 의 148. Sort List 문제와 똑같은 문제이며, 초반 세팅만 잘 하면 무난하게 풀 수 있는 문제이다.

접근 방법

• 테스트 케이스를 몇개 더 추가하여 완벽하게 풀려고 했다. 

Input: lists = [[], [], []]
Output: []

Input: lists = [[1], [], []]
Output: [1]

• 아주 많은 테스트 케이스 같은 경우에는 그냥 $500 * (10^4)$  쉽게 $10^5$라고 생각했기 때문에 $O(N log N)$이면 충분히 통과 될 것이라고 생각했다. => Merge Sort를 하자. 심지어 문제 제목에도 merge sort다.
• Merge Sort를 하기 위해서 나누어져 있는 링크드리스트들을 하나의 링크드리스트로 합할 필요가 있다고 생각했다. 
• 하나의 링크드 리스트로 만들었다면 기존에 풀었던 문제처럼 Divide and Conquer 를 활용하여 Merge Sort를 구현한다. 

이렇게 접근을 하였다. 구현한 코드를 뜯어보면서 정리해보자.

Main (mergeKLists)

나누어져 있는 링크드리스트들을 하나의 링크드리스트로 합치는 함수이자 문제 해결 함수이다.

for 반복문을 통하여 하나의 링크드리스트를 넣고 연결시킨 후 포인터를 마지막으로 이동시킨다. 

여기서 현재에 있는 노드가 1개 이하일 경우에는 바로 반환. 정렬할 수가 1개 이하이기 때문에 무의미하기 때문이다. 그러나 이 조건문을 넣은 이유는 빈 링크드 리스트로 구성되어 있을 수 있기 때문에 조건문을 1개 이하로 작성하였다. 

그게 아니라면 이제 분할하는 함수로 넘겨 정답을 찾는 과정을 진행한다.

divide 분할 함수

하나의 링크드리스트로 만들었다면, 이제 하나씩 분할하여 비교할 준비를 하자. 

1. 반환 조건을 작성하자. 현재의 노드가 비어있거나, 다음 노드가 비어있거나. 아마 대부분 다음노드가 비어있거나에서 걸리겠지만 이렇게 작성을 하였다.
2. 중간 지점을 계속해서 찾아서 하나가 남을 때 까지 나누자. 이때 리스트라면 mid = (left + right) / 2 를 하면 되지만, 링크드리스트이기 때문에 포인터를 slow는 한 번씩, fast는 두 번씩 건너뛰게 하여 fast가 마지막에 도달했을 때 slow의 위치는 mid가 된다. 
3. mid로 포인터를 옮긴 후 left, right를 정의하자.
4. left는 가장 앞이 되는 head, right는 그 다음이 되는 mid가 된다. 
5. 하나의 노드로 모두 분리 하였다면 이젠 합치자

 

merge 정복 함수

이제 정복하는, 합치는 과정이다.

1. 새로운 링크드리스트를 하나 만들고 초기값으로 가장 작은 값보다 하나 더 작은 값인 $-10^5 - 1$ 값으로 두자. 오름차순이니까 가장 작은 수가 되어야 한다. 
2. 이제 비교하자. left와 right 둘 중 하나가 빌 때 까지 진행한다. 비교는 따로 설명 안하겠다. 
3. 그리고 마지막에 둘 중 하나가 남기 때문에 남은 노드 혹은 노드들을 붙인다. 
4. return. 

어렵다면 어려운 문제였지만 역시 동작 구분을 하여 하나씩 구현하니 못 풀 문제도 아니었다. 처음에 divide 함수에 return 조건을 작성 안했더니 테스트케이스에서 시간초과가 났다. 그래서 살펴보니 return 조건을 안적었다. 그래서 작성을 하였더니 무난히 통과할 수 있었다. 

최근에 세그멘트 트리 조금 공부해본적이 있는데 저 트리도 약간 분할정복냄새가 나서 공부를 더 해볼 생각이다.

문제는 하나씩 잘 풀어나가고 있는데, 취업문은 잘 안풀린다. 모두 잘 풀리는 2026년이 되었으면 좋겠다.