Merge k Sorted Lists Visualizer

lists yellow = waiting in the heap · bottom row = merged, after the dashed dummy

heap {val, i} · 4₁ = value 4 from list 1 · smallest on top

public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<int[]> heap = new PriorityQueue<>( // {value, list} (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); for (int i = 0; i < lists.length; i++) { if (lists[i] != null) { // one head per list heap.offer(new int[]{lists[i].val, i}); } } ListNode dummy = new ListNode(); ListNode tail = dummy; while (!heap.isEmpty()) { int i = heap.poll()[1]; ListNode node = lists[i]; tail.next = node; tail = node; lists[i] = node.next; if (node.next != null) { // its successor takes its place heap.offer(new int[]{node.next.val, i}); } } return dummy.next;}

heap: —
popped: —
merged: —

Why it works

Brute force: collect all N values, sort, and build a new list: O(N log N) time and N new nodes. Merging the lists one after another into a growing result is O(N·k).
The next smallest node is always one of the k current heads, because every list is sorted. A min-heap holds exactly those heads; popping the root gives the next node of the answer, and that node's successor replaces it in the heap.
O(N log k): each of the N nodes is pushed and popped once, and the heap never holds more than k entries, so each operation costs O(log k). The heap is the only extra space: O(k).
Pitfall: ties. ListNode and int[] are not Comparable, so a PriorityQueue built without a comparator throws ClassCastException. The comparator here orders by value, then by list index i, so equal values always leave the heap in the same order.
Pitfall: empty lists. lists can have length 0 or contain null heads (empty lists); lists[i] != null keeps them out of the heap.
Alternative: merge the lists in pairs, round after round (divide and conquer), reusing Merge Two Sorted Lists (21). Also O(N log k), and O(1) extra space when done iteratively.