DSA-072 · K-way minimum frontier with identity-preserving splicing

Merge K Sorted Lists

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 4017 deterministic checks. Learner drafts are not executed.

Understand the problem

Merge k sorted acyclic singly linked lists into one sorted chain by reusing their original nodes. Return its head. Resolve equal values by source-list index, preserving each source’s original identity order.

lists is a nonnull Node[] with at most 10,000 heads and at most 100,000 total reachable nodes. Each source is sorted nondecreasing, acyclic, and node-disjoint from every other source. These structural/order promises are preconditions, not validated with a retained visited set.
Empty source lists and an empty head array are valid; return null when all are empty. Output contains every original node exactly once, unchanged final int values, stable source-index ties, and a null tail. One private dummy is excluded from output.
The caller permits destructive next-link changes. The head array entries themselves remain unchanged, while references to original nodes observe their new links. Null head array throws NullPointerException. Shared tails or cycles are outside the API and can corrupt an unchecked merge.

Examples

Input: L0:[1,4,5], L1:[1,3,4], L2:[2,6]
Output: L0:0,L1:0,L2:0,L1:1,L0:1,L1:2,L0:2,L2:1
The first 1 tie favors source 0; the 4 tie also favors source 0. Every label is an original object.
Input: L0:[2,2], L1:[2,2]
Output: L0:0,L0:1,L1:0,L1:1
After extracting L0:0, its equal-valued successor still outranks every source-1 tie.
Input: [null,null]
Output: null
No source frontier exists and the dummy is not returned.

Before you start

Destructive stable two-list merge (DSA-050)
PriorityQueue cursors carrying source identity

Recognize the structure

Each sorted source exposes its smallest unconsumed node at its current head. A heap of those heads answers which source contributes the next global minimum. This is a node-reuse merge, so value copies or shared-tail inputs require different ownership contracts.

Try before revealing

Hint 1

What is the smallest unconsumed candidate from each sorted source?

Hint 2

Put only those candidates into a min-heap with source-index ties.

Hint 3

Poll, save the original successor, append the exact node, and offer only that source’s successor.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Collect source-labelled references and stable-sort them

Traverse every list into (node,source) records, sort by node value then source, and relink in that order. Stable sorting preserves order among equal nodes within one source. For L0:[1,4] and L1:[1,3], sorted original references are L0:0,L1:0,L1:1,L0:1. Cost O(k+N log(N+1)) time and O(N) records; the heap retains only one cursor per nonempty source.

Improve the baseline

Initialize one frontier per source

Offer each nonnull head with its source index. A safe comparator uses value then source index. A source never contributes more than one queued cursor.

Extract and preserve its successor

Poll the minimum cursor, save node.next, append that original node after tail, then queue only its saved successor. Saving before later link changes protects reachability of the unconsumed suffix.

Finish with a null tail

When no frontier remains, every source is exhausted. Clear tail.next explicitly and return dummy.next. The selected prefix ends at tail; during construction its current tail can still point into an unconsumed suffix.

Why it is correct

Frontier invariant

Before each extraction the queue contains the first unconsumed node of each nonempty source, and no other nodes. Every later source node is at least its frontier value.

Correct next identity

The minimum value/source cursor is the next node in the required total merge order. Advancing only that source restores the frontier invariant; source disjointness prevents selecting an already emitted physical object. Within-source order remains stable because successors cannot enter before predecessors are extracted.

Termination and ownership

Each extraction consumes one original node, so exactly N extractions exhaust finite acyclic sources. The final chain has the full ranked identity sequence and null termination. No replacement nodes or value writes occur, and the original head-array entries are never assigned.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;
public final class Solution {
    public static final class Node {
        public final int value;
        public Node next;
        public Node(int value) { this.value = value; }
    }
    private record Cursor(Node node, int source) {}
    private static final Comparator<Cursor> ORDER = Comparator.comparingInt((Cursor e) -> e.node.value).thenComparingInt(Cursor::source);
    public static Node merge(Node[] lists) {
        Objects.requireNonNull(lists, "lists");
        PriorityQueue<Cursor> heads = new PriorityQueue<>(ORDER);
        for (int i = 0; i < lists.length; i++) if (lists[i] != null) heads.offer(new Cursor(lists[i],i));
        Node dummy = new Node(0), tail = dummy;
        while (!heads.isEmpty()) {
            Cursor entry = heads.poll();
            Node node = entry.node;
            Node next = node.next;
            tail.next = node;
            tail = node;
            if (next != null) heads.offer(new Cursor(next,entry.source));
        }
        tail.next = null;
        return dummy.next;
    }
    public static Node baseline(Node[] lists) {
        Objects.requireNonNull(lists, "lists");
        ArrayList<Cursor> nodes = new ArrayList<>();
        for (int i = 0; i < lists.length; i++) for (Node p = lists[i]; p != null; p = p.next) nodes.add(new Cursor(p,i));
        nodes.sort(ORDER);
        Node dummy = new Node(0), tail = dummy;
        for (Cursor entry : nodes) { tail.next = entry.node; tail = entry.node; }
        tail.next = null;
        return dummy.next;
    }
}

Read the meaningful blocks

Carry source metadata

Value alone is insufficient for deterministic cross-source ties. The source index belongs in each cursor and is copied when its successor is offered.

Save next before attaching future nodes

The current original successor is the only path needed to advance that source. Do not follow a later overwritten tail link to infer its successor.

Ignore heap iteration

Only poll order determines output. The displayed queue is a sorted logical frontier, not the Java queue’s storage layout.

Complexity

For k source slots and N total nodes, time is O(k+N log(k+1)), including scanning empty source slots. Workspace is O(k) cursor state plus one dummy; output reuses N original nodes rather than allocating a new N-node chain.

The sorting baseline takes O(k+N log(N+1)) time and O(N) auxiliary records. Pairwise divide-and-conquer merging also takes O(N log(k+1)) merge work but needs separate analysis of source ties and auxiliary recursion/iteration state.

Exact-state walkthroughs

Reveal normal and boundary traces

Advance only the extracted source

Input: [[1,4,5],[1,3,4],[2,6]] · Returned chain identities: ["L0:0","L1:0","L2:0","L1:1","L0:1","L1:2","L0:2","L2:1"]

Step 1 of 11: Queue one original head per nonempty source.

Sources are sorted, acyclic and node-disjoint by precondition. A sorted logical heap display does not imply queue iteration order.

K-way merge — original identities and source frontiers

Original head slots: 0: L0:0 · 1: L1:0 · 2: L2:0. Tail: dummy. Dummy.next: null.

Queued source heads — minimum value/source first

L0:0: 1
L1:0: 1
L2:0: 2

L0:0: 1next → L0:1
L0:1: 4next → L0:2
L0:2: 5next → null
L1:0: 1next → L1:1
L1:1: 3next → L1:2
L1:2: 4next → null
L2:0: 2next → L2:1
L2:1: 6next → null

Selected sequence ending at tail: (empty). Cards stay in source identity order; the tail may still point into an unconsumed suffix until final termination.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
nodes	`[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L0:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":null},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L1:2"},{"id":"L1:2","source":1,"index":2,"value":4,"next":null},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L2:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]`
roots	`["L0:0","L1:0","L2:0"]`
heap	`[{"id":"L0:0","source":0,"index":0,"value":1},{"id":"L1:0","source":1,"index":0,"value":1},{"id":"L2:0","source":2,"index":0,"value":2}]`
selected	`[]`
tail	`"dummy"`
dummyNext	`null`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     public static final class Node {
 7         public final int value;
 8         public Node next;
 9         public Node(int value) { this.value = value; }
10     }
11     private record Cursor(Node node, int source) {}
12     private static final Comparator<Cursor> ORDER = Comparator.comparingInt((Cursor e) -> e.node.value).thenComparingInt(Cursor::source);
13     public static Node merge(Node[] lists) {
14         Objects.requireNonNull(lists, "lists");
15         PriorityQueue<Cursor> heads = new PriorityQueue<>(ORDER);
16         for (int i = 0; i < lists.length; i++) if (lists[i] != null) heads.offer(new Cursor(lists[i],i));
17         Node dummy = new Node(0), tail = dummy;
18         while (!heads.isEmpty()) {
19             Cursor entry = heads.poll();
20             Node node = entry.node;
21             Node next = node.next;
22             tail.next = node;
23             tail = node;
24             if (next != null) heads.offer(new Cursor(next,entry.source));
25         }
26         tail.next = null;
27         return dummy.next;
28     }
29     public static Node baseline(Node[] lists) {
30         Objects.requireNonNull(lists, "lists");
31         ArrayList<Cursor> nodes = new ArrayList<>();
32         for (int i = 0; i < lists.length; i++) for (Node p = lists[i]; p != null; p = p.next) nodes.add(new Cursor(p,i));
33         nodes.sort(ORDER);
34         Node dummy = new Node(0), tail = dummy;
35         for (Cursor entry : nodes) { tail.next = entry.node; tail = entry.node; }
36         tail.next = null;
37         return dummy.next;
38     }
39 }
40

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Queue one original head per nonempty source.
Sources are sorted, acyclic and node-disjoint by precondition. A sorted logical heap display does not imply queue iteration order.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L0:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":null},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L1:2"},{"id":"L1:2","source":1,"index":2,"value":4,"next":null},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L2:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[{"id":"L0:0","source":0,"index":0,"value":1},{"id":"L1:0","source":1,"index":0,"value":1},{"id":"L2:0","source":2,"index":0,"value":2}]
selected
[]
tail
"dummy"
dummyNext
null
phase
"initial"
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L0:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":null},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L1:2"},{"id":"L1:2","source":1,"index":2,"value":4,"next":null},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L2:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[{"id":"L1:0","source":1,"index":0,"value":1},{"id":"L2:0","source":2,"index":0,"value":2},{"id":"L0:1","source":0,"index":1,"value":4}]
selected
["L0:0"]
tail
"L0:0"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L0:0","source":0,"index":0,"value":1}
savedNext
"L0:1"
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L1:0"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L0:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":null},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L1:2"},{"id":"L1:2","source":1,"index":2,"value":4,"next":null},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L2:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[{"id":"L2:0","source":2,"index":0,"value":2},{"id":"L1:1","source":1,"index":1,"value":3},{"id":"L0:1","source":0,"index":1,"value":4}]
selected
["L0:0","L1:0"]
tail
"L1:0"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L1:0","source":1,"index":0,"value":1}
savedNext
"L1:1"
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L1:0"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L0:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":null},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L2:0"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L1:2"},{"id":"L1:2","source":1,"index":2,"value":4,"next":null},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L2:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[{"id":"L1:1","source":1,"index":1,"value":3},{"id":"L0:1","source":0,"index":1,"value":4},{"id":"L2:1","source":2,"index":1,"value":6}]
selected
["L0:0","L1:0","L2:0"]
tail
"L2:0"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L2:0","source":2,"index":0,"value":2}
savedNext
"L2:1"
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L1:0"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L0:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":null},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L2:0"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L1:2"},{"id":"L1:2","source":1,"index":2,"value":4,"next":null},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L1:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[{"id":"L0:1","source":0,"index":1,"value":4},{"id":"L1:2","source":1,"index":2,"value":4},{"id":"L2:1","source":2,"index":1,"value":6}]
selected
["L0:0","L1:0","L2:0","L1:1"]
tail
"L1:1"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L1:1","source":1,"index":1,"value":3}
savedNext
"L1:2"
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L1:0"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L0:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":null},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L2:0"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L0:1"},{"id":"L1:2","source":1,"index":2,"value":4,"next":null},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L1:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[{"id":"L1:2","source":1,"index":2,"value":4},{"id":"L0:2","source":0,"index":2,"value":5},{"id":"L2:1","source":2,"index":1,"value":6}]
selected
["L0:0","L1:0","L2:0","L1:1","L0:1"]
tail
"L0:1"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L0:1","source":0,"index":1,"value":4}
savedNext
"L0:2"
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L1:0"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L1:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":null},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L2:0"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L0:1"},{"id":"L1:2","source":1,"index":2,"value":4,"next":null},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L1:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[{"id":"L0:2","source":0,"index":2,"value":5},{"id":"L2:1","source":2,"index":1,"value":6}]
selected
["L0:0","L1:0","L2:0","L1:1","L0:1","L1:2"]
tail
"L1:2"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L1:2","source":1,"index":2,"value":4}
savedNext
null
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L1:0"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L1:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":null},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L2:0"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L0:1"},{"id":"L1:2","source":1,"index":2,"value":4,"next":"L0:2"},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L1:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[{"id":"L2:1","source":2,"index":1,"value":6}]
selected
["L0:0","L1:0","L2:0","L1:1","L0:1","L1:2","L0:2"]
tail
"L0:2"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L0:2","source":0,"index":2,"value":5}
savedNext
null
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L1:0"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L1:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":"L2:1"},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L2:0"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L0:1"},{"id":"L1:2","source":1,"index":2,"value":4,"next":"L0:2"},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L1:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[]
selected
["L0:0","L1:0","L2:0","L1:1","L0:1","L1:2","L0:2","L2:1"]
tail
"L2:1"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L2:1","source":2,"index":1,"value":6}
savedNext
null
Terminate the reused output chain explicitly.
Every original identity occurs once in value/source order, and original head-array slots remain unchanged.
nodes
[{"id":"L0:0","source":0,"index":0,"value":1,"next":"L1:0"},{"id":"L0:1","source":0,"index":1,"value":4,"next":"L1:2"},{"id":"L0:2","source":0,"index":2,"value":5,"next":"L2:1"},{"id":"L1:0","source":1,"index":0,"value":1,"next":"L2:0"},{"id":"L1:1","source":1,"index":1,"value":3,"next":"L0:1"},{"id":"L1:2","source":1,"index":2,"value":4,"next":"L0:2"},{"id":"L2:0","source":2,"index":0,"value":2,"next":"L1:1"},{"id":"L2:1","source":2,"index":1,"value":6,"next":null}]
roots
["L0:0","L1:0","L2:0"]
heap
[]
selected
["L0:0","L1:0","L2:0","L1:1","L0:1","L1:2","L0:2","L2:1"]
tail
"L2:1"
dummyNext
"L0:0"
phase
"finished"
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
["L0:0","L1:0","L2:0","L1:1","L0:1","L1:2","L0:2","L2:1"]

Equal-value ties preserve whole source prefixes

Input: [[2,2],[2,2]] · Returned chain identities: ["L0:0","L0:1","L1:0","L1:1"]

Step 1 of 7: Queue one original head per nonempty source.

Sources are sorted, acyclic and node-disjoint by precondition. A sorted logical heap display does not imply queue iteration order.

K-way merge — original identities and source frontiers

Original head slots: 0: L0:0 · 1: L1:0. Tail: dummy. Dummy.next: null.

Queued source heads — minimum value/source first

L0:0: 2
L1:0: 2

L0:0: 2next → L0:1
L0:1: 2next → null
L1:0: 2next → L1:1
L1:1: 2next → null

Selected sequence ending at tail: (empty). Cards stay in source identity order; the tail may still point into an unconsumed suffix until final termination.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
nodes	`[{"id":"L0:0","source":0,"index":0,"value":2,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":2,"next":null},{"id":"L1:0","source":1,"index":0,"value":2,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":2,"next":null}]`
roots	`["L0:0","L1:0"]`
heap	`[{"id":"L0:0","source":0,"index":0,"value":2},{"id":"L1:0","source":1,"index":0,"value":2}]`
selected	`[]`
tail	`"dummy"`
dummyNext	`null`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     public static final class Node {
 7         public final int value;
 8         public Node next;
 9         public Node(int value) { this.value = value; }
10     }
11     private record Cursor(Node node, int source) {}
12     private static final Comparator<Cursor> ORDER = Comparator.comparingInt((Cursor e) -> e.node.value).thenComparingInt(Cursor::source);
13     public static Node merge(Node[] lists) {
14         Objects.requireNonNull(lists, "lists");
15         PriorityQueue<Cursor> heads = new PriorityQueue<>(ORDER);
16         for (int i = 0; i < lists.length; i++) if (lists[i] != null) heads.offer(new Cursor(lists[i],i));
17         Node dummy = new Node(0), tail = dummy;
18         while (!heads.isEmpty()) {
19             Cursor entry = heads.poll();
20             Node node = entry.node;
21             Node next = node.next;
22             tail.next = node;
23             tail = node;
24             if (next != null) heads.offer(new Cursor(next,entry.source));
25         }
26         tail.next = null;
27         return dummy.next;
28     }
29     public static Node baseline(Node[] lists) {
30         Objects.requireNonNull(lists, "lists");
31         ArrayList<Cursor> nodes = new ArrayList<>();
32         for (int i = 0; i < lists.length; i++) for (Node p = lists[i]; p != null; p = p.next) nodes.add(new Cursor(p,i));
33         nodes.sort(ORDER);
34         Node dummy = new Node(0), tail = dummy;
35         for (Cursor entry : nodes) { tail.next = entry.node; tail = entry.node; }
36         tail.next = null;
37         return dummy.next;
38     }
39 }
40

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Queue one original head per nonempty source.
Sources are sorted, acyclic and node-disjoint by precondition. A sorted logical heap display does not imply queue iteration order.
nodes
[{"id":"L0:0","source":0,"index":0,"value":2,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":2,"next":null},{"id":"L1:0","source":1,"index":0,"value":2,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":2,"next":null}]
roots
["L0:0","L1:0"]
heap
[{"id":"L0:0","source":0,"index":0,"value":2},{"id":"L1:0","source":1,"index":0,"value":2}]
selected
[]
tail
"dummy"
dummyNext
null
phase
"initial"
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":2,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":2,"next":null},{"id":"L1:0","source":1,"index":0,"value":2,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":2,"next":null}]
roots
["L0:0","L1:0"]
heap
[{"id":"L0:1","source":0,"index":1,"value":2},{"id":"L1:0","source":1,"index":0,"value":2}]
selected
["L0:0"]
tail
"L0:0"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L0:0","source":0,"index":0,"value":2}
savedNext
"L0:1"
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":2,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":2,"next":null},{"id":"L1:0","source":1,"index":0,"value":2,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":2,"next":null}]
roots
["L0:0","L1:0"]
heap
[{"id":"L1:0","source":1,"index":0,"value":2}]
selected
["L0:0","L0:1"]
tail
"L0:1"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L0:1","source":0,"index":1,"value":2}
savedNext
null
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":2,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":2,"next":"L1:0"},{"id":"L1:0","source":1,"index":0,"value":2,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":2,"next":null}]
roots
["L0:0","L1:0"]
heap
[{"id":"L1:1","source":1,"index":1,"value":2}]
selected
["L0:0","L0:1","L1:0"]
tail
"L1:0"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L1:0","source":1,"index":0,"value":2}
savedNext
"L1:1"
Append the exact extracted node and advance only its source.
The saved original successor remains reachable. The selected sequence ends at tail, whose link may still reach an unconsumed suffix.
nodes
[{"id":"L0:0","source":0,"index":0,"value":2,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":2,"next":"L1:0"},{"id":"L1:0","source":1,"index":0,"value":2,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":2,"next":null}]
roots
["L0:0","L1:0"]
heap
[]
selected
["L0:0","L0:1","L1:0","L1:1"]
tail
"L1:1"
dummyNext
"L0:0"
phase
"emit"
popped
{"id":"L1:1","source":1,"index":1,"value":2}
savedNext
null
Terminate the reused output chain explicitly.
Every original identity occurs once in value/source order, and original head-array slots remain unchanged.
nodes
[{"id":"L0:0","source":0,"index":0,"value":2,"next":"L0:1"},{"id":"L0:1","source":0,"index":1,"value":2,"next":"L1:0"},{"id":"L1:0","source":1,"index":0,"value":2,"next":"L1:1"},{"id":"L1:1","source":1,"index":1,"value":2,"next":null}]
roots
["L0:0","L1:0"]
heap
[]
selected
["L0:0","L0:1","L1:0","L1:1"]
tail
"L1:1"
dummyNext
"L0:0"
phase
"finished"
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
["L0:0","L0:1","L1:0","L1:1"]

All sources empty

Input: [[],[]] · Returned chain identities: []

Step 1 of 3: Queue one original head per nonempty source.

Sources are sorted, acyclic and node-disjoint by precondition. A sorted logical heap display does not imply queue iteration order.

K-way merge — original identities and source frontiers

Original head slots: 0: null · 1: null. Tail: dummy. Dummy.next: null.

Queued source heads — minimum value/source first

Empty.

Selected sequence ending at tail: (empty). Cards stay in source identity order; the tail may still point into an unconsumed suffix until final termination.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
nodes	`[]`
roots	`[null,null]`
heap	`[]`
selected	`[]`
tail	`"dummy"`
dummyNext	`null`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     public static final class Node {
 7         public final int value;
 8         public Node next;
 9         public Node(int value) { this.value = value; }
10     }
11     private record Cursor(Node node, int source) {}
12     private static final Comparator<Cursor> ORDER = Comparator.comparingInt((Cursor e) -> e.node.value).thenComparingInt(Cursor::source);
13     public static Node merge(Node[] lists) {
14         Objects.requireNonNull(lists, "lists");
15         PriorityQueue<Cursor> heads = new PriorityQueue<>(ORDER);
16         for (int i = 0; i < lists.length; i++) if (lists[i] != null) heads.offer(new Cursor(lists[i],i));
17         Node dummy = new Node(0), tail = dummy;
18         while (!heads.isEmpty()) {
19             Cursor entry = heads.poll();
20             Node node = entry.node;
21             Node next = node.next;
22             tail.next = node;
23             tail = node;
24             if (next != null) heads.offer(new Cursor(next,entry.source));
25         }
26         tail.next = null;
27         return dummy.next;
28     }
29     public static Node baseline(Node[] lists) {
30         Objects.requireNonNull(lists, "lists");
31         ArrayList<Cursor> nodes = new ArrayList<>();
32         for (int i = 0; i < lists.length; i++) for (Node p = lists[i]; p != null; p = p.next) nodes.add(new Cursor(p,i));
33         nodes.sort(ORDER);
34         Node dummy = new Node(0), tail = dummy;
35         for (Cursor entry : nodes) { tail.next = entry.node; tail = entry.node; }
36         tail.next = null;
37         return dummy.next;
38     }
39 }
40

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Queue one original head per nonempty source.
Sources are sorted, acyclic and node-disjoint by precondition. A sorted logical heap display does not imply queue iteration order.
nodes
[]
roots
[null,null]
heap
[]
selected
[]
tail
"dummy"
dummyNext
null
phase
"initial"
Terminate the reused output chain explicitly.
Every original identity occurs once in value/source order, and original head-array slots remain unchanged.
nodes
[]
roots
[null,null]
heap
[]
selected
[]
tail
"dummy"
dummyNext
null
phase
"finished"
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
[]

Test the contract

Input: No sources/all empty sources
Output: null
Empty frontier.
Input: Multiple all-equal sources
Output: Source index, then original source order
Stable tie identity.
Input: MIN/MAX source values
Output: Safe sorted output
No subtracting comparator.
Input: One 100,000-node source
Output: Same node identities in order
Size boundary.
Input: 10,000 singleton sources
Output: All nodes exactly once; head slots unchanged
Wide frontier.

Common mistakes and counterexamples

Allow shared tails without defining alias semantics

Counterexample: Two heads equal to X can cause the same object to be appended twice and form a self-loop.

Require node-disjoint inputs or design a different once-per-identity merge.

Compare only values

Counterexample: Equal nodes from later sources can appear before earlier-source ties.

Include source index in the total comparator.

Replace nodes with copied values

Counterexample: The value sequence may look correct while every required identity is lost.

Test exact original references, their count, and tail termination.

Mutate the head array to advance sources

Counterexample: Callers retaining lists[] would observe different heads despite the contract.

Keep source cursors in the heap, leaving array slots unchanged.

Follow-ups

Use pairwise divide and conquer.

Merge adjacent source ranges while retaining source metadata or a grouping order that preserves earlier-source equal ties. Analyze the recursion stack and reuse the two-list identity tests.

Merge sorted streams instead of mutable lists.

The frontier argument still applies, but input nodes may not exist or may be read-only. Return fresh output or emit values; define stream failure/backpressure behavior separately.

Suppress duplicate values.

That changes occurrence coverage and potentially which original node identity survives. State a representative policy and detach or otherwise account for skipped nodes rather than silently changing the current merge.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 121/20,000 characters

Self-review

I prove one queued head per active source is sufficient.I state disjoint ownership and save successors before rewiring.I test original identities and the unchanged head array, not only values.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Heaps: retain the useful frontier

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external platform-difficulty claims.