Leetcode 23. Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/

Merging one at one time is too slow, so we try to use divide and conquer method to achieve better performance. Or we can use the heapq module to do the task: first put all starting nodes to heap, pop the smallest one to result linked list and then fill the blank with popped node's  next node and go on.

Solution 1:

# T:O(nlgk) S:O(k)
class Solution:
    # @param {ListNode[]} lists
    # @return {ListNode}
    def mergeKLists(self, lists):
        L = len(lists)
        if L == 0:
            return None
        if L == 1:
            return lists[0]
        mid = L//2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        dummy = ListNode(0)
        cur = dummy
        while left or right:
            if right == None or (left and left.val <= right.val):
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        return dummy.next

Run Time: 692 ms

Solution 2:

# T:O(nlgk) S:O(k)
import heapq
class Solution:
    # @param a list of ListNode
    # @return a ListNode
    def mergeKLists(self, lists):
        dummy = ListNode(0)
        current = dummy
        
        heap = []
        for sorted_list in lists:
            if sorted_list:
                heapq.heappush(heap, (sorted_list.val, sorted_list))
                
        while heap:
            smallest = heapq.heappop(heap)[1]
            current.next = smallest
            current = current.next
            if smallest.next:
                heapq.heappush(heap, (smallest.next.val, smallest.next))
                
        return dummy.next

Run Time: 396 ms