Amazon — Merge K Sorted Lists (Min-Heap)

[1→4→5, 1→3→4, 2→6]
→ 1→1→2→3→4→4→5→6

import heapq

def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = curr = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

function mergeKLists(lists) {
    const dummy = {val:0,next:null}; let cur=dummy;
    const q=lists.filter(Boolean).map(n=>[n.val,n]);
    q.sort((a,b)=>a[0]-b[0]);
    while(q.length){
        let mn=0; for(let i=1;i<q.length;i++) if(q[i][0]<q[mn][0]) mn=i;
        const [,node]=q.splice(mn,1)[0];
        cur.next=node; cur=cur.next;
        if(node.next) q.push([node.next.val,node.next]);
    }
    return dummy.next;
}

import java.util.*;
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq=new PriorityQueue<>(Comparator.comparingInt(n->n.val));
    for (ListNode n:lists) if(n!=null) pq.offer(n);
    ListNode dummy=new ListNode(0),cur=dummy;
    while (!pq.isEmpty()) {
        cur.next=pq.poll(); cur=cur.next;
        if (cur.next!=null) pq.offer(cur.next);
    }
    return dummy.next;
}

#include <queue>
using namespace std;
ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp=[](ListNode* a,ListNode* b){return a->val>b->val;};
    priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> pq(cmp);
    for (auto n:lists) if(n) pq.push(n);
    ListNode dummy(0),*cur=&dummy;
    while (!pq.empty()){cur->next=pq.top();pq.pop();cur=cur->next;if(cur->next)pq.push(cur->next);}
    return dummy.next;
}

/* C: array of current pointers, find min in O(k) each step → O(nk) */
/* Heap optimization: same pattern as Python above */