Merge k Sorted Lists Solved

Problem:

You are given an array of k linked-lists lists, each linked list is sorted in ascending order.

Merge all the linked lists into one sorted linked list and return it.

Example 1:

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

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i]. length will not exceed 104.

Python Code:

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap=[]
        result=ListNode()
        pointer=result
        for i in range(len(lists)):
            if not lists[i] is None:
                heapq.heappush(heap,(lists[i].val,i))
        while len(heap)>0:
            temp=heapq.heappop(heap)
            if not lists[temp[1]] is None:
                lists[temp[1]]=lists[temp[1]].next
                if not lists[temp[1]] is None:
                    heapq.help push(heap,(lists[temp[1]].val,temp[1]))
            pointer.next=ListNode(temp[0])
            pointer=pointer.next
        return result.next

Java Code:

public ListNode mergeKLists(ListNode[] lists) 
{
   PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
   for(ListNode node: lists){
     if(node != null)
       minHeap.add(node);
   }
   ListNode result = new ListNode(0), current = result;
   while(!minHeap.isEmpty())
  {
     ListNode minNode = minHeap.remove();
     current.next = minNode;
     if(minNode.next != null)
       minHeap.add(minNode.next);
     current = current.next;
   }
   return result.next;
 }

Explanation:

Initially, you are looking for the first number of the solution. The first number of the solution has to be the first element of one list because since the lists are sorted, the first element of each list is the smallest. For the second element of the solution, the same system is used, but in this case, you cannot choose the element you already took.

After doing the math, if you keep a pointer in each list indicating the possible positions you can choose on them, you just have to figure out how to compare them. You can use a heap to compare all the numbers you are pointing to in each step in Big O(1) time complexity. You have to keep the numbers you are pointing to inside the heap and then choose the smallest of the heap during each step. Then, add it to the result list, remove it from the heap and add to the heap the element next to it in its original list.

Merge_K_Linked_List_Solved_II.mp4

Time Complexity:

The time complexity of this algorithm is Big O of the sum of all the list lengths since we are going through each element of each list doing O(1) time complexity operations in each list.