Merge k Sorted Lists

Question

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Tags

• Linked List
• heap
• Divide and Conquer

Thought

Push the head node of each linked list into a heap and pop out in the sorted order and push a new node back into the heap until the heap is empty.

Code

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


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            if node:
                heap.append((node.val, node))
        heapq.heapify(heap)
        dummy = ListNode(0)
        current = dummy
        while heap:
            pop = heapq.heappop(heap)
            current.next = pop[1]
            current = current.next
            if pop[1].next:
                heapq.heappush(heap, (pop[1].next.val, pop[1].next))
        return dummy.next