LC 23

Solution to LeetCode 23 Merge k sorted lists.

LeetCode 23

Merge k sorted lists (Hard). [link]

1. Min-heap. Insert the head of all lists into a min-heap.

   While heap is not empty: 1) pop the min value from the heap and link to the new linked list, 2) add it to the new linked list, 3) break the list and move the pointer to the next, 4) delete the element in the list that we have gone through, 5) push the next element in that list to the heap.

   The time complexity is O(nk log k), where n is the length of each lists, k is the number of lists, nk is the number of elements, the max size of heap is k. The space complexity is O(k) + O(n).

# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        tail = dummy = ListNode(0)
        heap = []
        heapq.heapify(heap)
        [heapq.heappush(heap, (l.val, i)) for i, l in enumerate(lists) if l] # push head of each list and the corresponding index of list
        while heap:        
            curVal, curIndex = heapq.heappop(heap) # pop min value list by list
            curHead = lists[curIndex] # curHead is always the min value popped from heap
            curNext = curHead.next # store the next node
            tail.next = curHead # link tail to curHead
            curHead.next = None # break the list, keep the curHead

            tail = curHead # move tail pointer to the next
            curHead = curNext # move curHead to the next
            
            if curHead: # stop when curNext = None
                lists[curIndex] = curHead # remove the first element from that list
                heapq.heappush(heap,(curHead.val, curIndex)) # push the next element from that list to heap
        return dummy.next

2. Divide and conquer - Merge Sort.

   Time complexity is O(nk log k), where the height of the tree is log k, O(nk) will take for each layer. Space complexity O(log k) if we use recursion, smaller than method (1) min heap. Space complexity can be O(1) if we apply non-recursion algorithm. [How to implement non-recursion merge sort? I will write a post later.]

   # class ListNode(object):
   #     def __init__(self, val=0, next=None):
   #         self.val = val
   #         self.next = next
   class Solution(object):
       def mergeKLists(self, lists):
           """
           :type lists: List[ListNode]
           :rtype: ListNode
           """
           if not lists: return
           return self.merge(lists, 0, len(lists) -1)
       
       def merge(self, lists, l, r):
           if l == r:
               return lists[l]
           m = l + (r - l) // 2
           l1 = self.merge(lists, l, m)
           l2 = self.merge(lists, m + 1, r)
           return self.mergeTwoLists(l1, l2)
       
       def mergeTwoLists(self, l1, l2):
           if not l1: return l2
           if not l2: return l1
           
           if l1.val < l2.val:
               l1.next = self.mergeTwoLists(l1.next, l2)
               return l1
           else:
               l2.next = self.mergeTwoLists(l2.next, l1)
               return l2