23. Merge k Sorted Lists (Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort)

링크 - https://leetcode.com/problems/merge-k-sorted-lists/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

1) Heap

우리는 Heap을 통해서 각 node의 값들을 작은 순서대로 추적이 가능하다. 이를 위해서는 새로운 클래스를 만들고 __lt__메서드를 생성해야 한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class HeapNode:
    def __init__(self, node):
        self.node = node

    def __lt__(self, other):
        return self.node.val < other.node.val


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        node = dummy
        heap = []

        for l in lists:
            if l:
                heapq.heappush(heap, HeapNode(l))

        while heap:
            heap_node = heapq.heappop(heap)
            new_node = ListNode(heap_node.node.val)
            node.next = new_node
            node = node.next
            if heap_node.node.next:
                heapq.heappush(heap, HeapNode(heap_node.node.next))

        return dummy.next

Time Complexity: O(NlogK) 여기서 k는 linked list의 개수이다.

Space Complexity: O(n) -> 새로운 링크드 리스트, O(k) -> heap이 차지하는 공간

2) Merge with Divide and Conquer

우리는 linked list들을 나눠서 2개씩 merge한 후, 합치는 방법을 사용할 수 있다.

# 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]:
        n = len(lists)
        interval = 1
        while interval < n:
            for i in range(0, n - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i+interval])
            interval *= 2

        return lists[0] if n > 0 else None
    
    def merge2Lists(self, l1, l2):
        head = point = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l2.next
            point = point.next

        if l1:
            point.next = l1
        elif l2:
            point.next = l2

        return head.next

Time Complexity: O(NlogK) 여기서 k는 linked list의 개수이다.

Space Complexity: O(1)