23.md

23 Merge k Sorted Lists

Description

link

---

General Type

K - Merge - Problems

• Heap

---

Solution

• set priority quene of the first number in each lists as (n.val, i, n) # means n.val to be the key

• pop the smallest one and add it to dummy's next

• pus the popped one's next node to the pq

• return res (the first dummy node)

---

Code

Complexity T : O(Nlog(len(Lists)))

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

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        pq = [(n.val, i, n) for i, n in enumerate(lists) if n]
        heapq.heapify(pq)
        res = dummy = ListNode(0)
        
        while pq:
            v, i, n = heapq.heappop(pq)
            dummy.next = n
            dummy = dummy.next
            n = n.next
            if n:
                heapq.heappush(pq, (n.val, i, n))
        return res.next