23. Merge k Sorted Lists (Python)

Related Topic

Heap.

Description

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

Sample I/O

Example 1

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Methodology

We create a min heap to maintaine all nodes’ value and create a node with value by polling the heap and linked it to previous node until the heap is empty.

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        heap = []
        root = res = ListNode(None)
        for l in lists:
            while l:
                heappush(heap, l.val)
                l = l.next
        while heap:
            res.next = ListNode(heappop(heap))
            res = res.next
        return root.next

BigO

We iterate the list once and inside the each list we will iterate each node so the time complexity is O(N*M) where N is the length of the lists and M is length of each list.