Leet Code : Merge k Sorted Lists C++ , Java , Python solution

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: []

C++ Solution :

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        if(lists.empty()) return nullptr;
        ListNode* dummy = new ListNode(0);
        ListNode* cp = dummy;
        int cur = INT_MAX, index = 0;
        while(1) {
            cur = INT_MAX;
            for(int i=0;i<lists.size();++i) {
                if(lists[i] != NULL && lists[i]->val<cur) {
                    cur = lists[i]->val;
                    cp->next = lists[i];
                    index = i;
                }
            }
            if(cur == INT_MAX) break;
            lists[index] = lists[index]->next;
            cp = cp->next;
        }
        
        return dummy->next;

    }
};

Java Solution :

Approach : Using Priority Queue
Step 1 : Convert Array of ListNode into PriorityQueue
Step 2 : Create a LinkedList with values from PriorityQueue
class Solution {
    public ListNode mergeKLists(ListNode[] lists)
    {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // converting into Priority Queue
        for(ListNode a : lists)
        {
            while(a != null)
            {
                pq.add(a.val);
                a = a.next;
            }
        }
        
        // Converting back to Linked List
        ListNode ans = new ListNode();
        if(pq.size() == 0)
        {
            return null;
        }
        else
        {
            ans.val = pq.poll();
            ListNode temp = ans;
            while(pq.size() != 0)
            {
                temp.next = new ListNode(pq.poll());
                temp = temp.next;
            }
            return ans;
        } 
    }
}

Python Solution

 def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        
        n = len(lists)
        if n == 0:
            return None
        
        if n == 1:
            return lists[0]
        
        init = [(lists[i].val, i) for i in range(n) if lists[i]]
        if not init:
            return None
        
        heapq.heapify(init)
        result = ListNode()
        head = result
        while init:
            value, index = heapq.heappop(init)
            #index is the index of listnode
            head.next = lists[index]
            head = head.next
            lists[index] = lists[index].next
            #may be we push something
            if not lists[index]:
                continue
            newValue = lists[index].val
            if newValue < value:
                #add this value to result and continue
                head.next = lists[index]
                lists[index] = lists[index].next
                head = head.next
                continue
            heapq.heappush(init, (newValue,index))
            
        return result.next