LC 0023 [H] Merge k Sorted Lists - ALawliet/algorithms GitHub Wiki

# O(nlogk)
from queue import PriorityQueue

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
      Q = PriorityQueue()
      dum = ListNode(-1)
        
      for head in lists:
        cur = head
        while cur:
          Q.put(cur.val)
          cur = cur.next
            
      cur = dum
      while Q.qsize(): # > 0, not Q.empty()
        cur.next = ListNode(Q.get())
        cur = cur.next
      
      return dum.next

# mergesort: O(nlogn)
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists: return 
        if len(lists) == 1: return lists[0]
        m = len(lists) // 2
        l = self.mergeKLists(lists[:m])
        r = self.mergeKLists(lists[m:])
        return self.merge(l, r)

    def merge(self, l, r): # merge 2 sorted lists
        dum = ListNode(-1)
        cur = dum

        while l and r:
            if l.val < r.val:
                cur.next = l
                l = l.next
            else:
                cur.next = r
                r = r.next
            cur = cur.next

        cur.next = l or r

        return dum.next