Merge K Sorted Linked List

Given 3 sorted linkedlist, you need to find a way to merge these 3 separated linkedlist.

To do this, just use a heaps,

1. Add the first element of each list to a heap. After this, we already know which one is the smallest of the three by heappop()
2. For the linkedlist that was popped in heappop() we increment it and add it to the heap again

Time Complexity: $O(nlogn)$

• We have to perform heappush() and heappop() for $n$ elements

Space Complexity: $O(n)$

• New sorted array to store $n$ elements

Ways to identify:

• When we want to cross sort multiple sorted array

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

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Note: in here we have to use Primary Queue. We need to update the head of each list to the lastest item. So we store in the priority queue (priority, index) so that we can go back to that item and move the head

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []

        # 1. Add everything to the heap
        for i, head in enumerate(lists):
            if head:
                heapq.heappush(heap, (head.val, i))

        mergedList = ListNode()
        curr = mergedList

        while heap:
            _, smallestIndex = heapq.heappop(heap)
            smallestNode = lists[smallestIndex]

            curr.next = smallestNode
            curr = curr.next

            lists[smallestIndex] = lists[smallestIndex].next
            nextNode = lists[smallestIndex]

            if nextNode:
                heapq.heappush(heap, (nextNode.val, smallestIndex))

        return mergedList.next