DSA-050 · FOCUSED PRACTICE

Merge Two Sorted Lists

Core · Java 21 · Version 1 · editorial draft

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

Understand the problem

Merge two sorted singly linked lists into one sorted list by relinking the original nodes. Return its head. Preserve order within each input; when values tie, nodes from input A precede nodes from input B.

Each input is null or a finite acyclic singly linked list of at most 100,000 nodes, sorted in nondecreasing int value order. Node.value is final and Node.next is mutable. These are preconditions, not runtime validation steps.
The two inputs must be node-disjoint: they may contain equal values but must not share even a tail node. Shared nodes, cycles, or unsorted inputs are outside this API contract. The merge is destructive: the caller grants permission to rewrite next links.
Return null when both inputs are null. The output contains every original node exactly once, no replacement nodes, unchanged values, and a null tail. A single temporary dummy node is allocated but is never part of the output.
Within each input, original identity order is stable. Among equal-valued nodes across inputs, all A occurrences precede B occurrences. The caller must use the returned head; aliases to original nodes observe the new links.

Examples

Input: A: A0(1) → A1(3); B: B0(2) → B1(4)
Output: A0 → B0 → A1 → B1 → null
The returned reference is A0. Choosing A0 then B0 rewrites A0.next from A1 to B0; no value is copied.
Input: A: A0(2) → A1(2); B: B0(2)
Output: A0 → A1 → B0 → null
The <= comparison selects A on every tie, preserving the declared cross-input stability.
Input: A: null; B: B0(7) → B1(9)
Output: B0 → B1 → null
Attach B as a suffix and return the original B0. No input link needs changing.

Before you start

Reference identity versus equal integer values
Sorted streams and greedy frontier selection
Dummy head and mutable next fields

Recognize the structure

Two already sorted streams expose their smallest remaining candidates at their heads. Relinking is appropriate because ownership permits mutation and node identities must survive. Sorting copied values would lose identity; merging shared-tail lists requires a different alias-aware contract.

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 · 125/20,000 characters

Self-review

I can explain why only the two heads need comparison.I distinguish the selected prefix ending at tail from the possibly still linked remaining suffix.I test stability by reference identity and understand why shared nodes violate the contract.

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

Try before revealing

Hint 1

The smaller of the two current heads must be the next output node. What tie rule is promised?

Hint 2

A dummy predecessor lets the first node use exactly the same linking operation as later nodes.

Hint 3

Link the selected head, advance that source, advance tail, then attach the nonempty suffix.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Collect references and stable-sort

Collect A references in source order, then B references, stable-sort by int value using Comparator.comparingInt, and relink adjacent references with a final null. For A0(1)→A1(3) and B0(2)→B1(3), collection [A0,A1,B0,B1] sorts to [A0,B0,A1,B1]. Java List.sort is stable, so equal A1 precedes B1. This valid destructive baseline uses O(n+m) reference storage and O((n+m) log(n+m)) time as an upper bound. Subtracting values in a comparator can overflow; the implementation does not do that.

Improve the baseline

Use sorted frontiers

If a and b both exist, the next output node must be the smaller head: every other remaining node is at least its own head. When equal, choose a to honor A-before-B ties.

Make the empty prefix ordinary

Let dummy.next denote the eventual result and tail the last selected node, initially dummy. Set tail.next to the selected original node, advance only that source cursor, then advance tail. Save the source successor through its unchanged link before a later iteration rewrites the new tail link.

Attach the remaining chain once

When one cursor is null, the other suffix is sorted and every remaining value is at least the final selected value. One assignment attaches the whole suffix. Return dummy.next, never the dummy itself.

Why it is correct

Initial prefix

Before the first iteration, zero nodes have been selected, tail is dummy, and the two cursors root the complete disjoint inputs.

Inductive selection and identity

At each loop boundary the selected sequence, ending at tail, is exactly the stable merge of the consumed prefixes. Its internal edges are final; tail.next may still point into an unconsumed suffix, so the selected prefix is a conceptual sequence ending at tail, not necessarily a null-terminated standalone list. Each source cursor roots its untouched remaining suffix. Selecting the smaller head (A on ties) appends the only correct next identity. Disjoint inputs ensure the node has not already been selected and cannot point back into the prefix.

Progress and suffix

One cursor advances on each iteration, so at most n+m selections occur. Once a source is empty, all nodes in the other suffix belong next in their existing order. Attaching that acyclic disjoint suffix gives every input identity exactly once and a null tail; dummy is excluded by returning dummy.next.

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;

public final class Solution {
    public static final class Node {
        public final int value;
        public Node next;
        public Node(int value) { this.value = value; }
    }

    // Inputs must be sorted, acyclic, and node-disjoint. Reuses their nodes.
    public static Node merge(Node a, Node b) {
        Node dummy = new Node(0);
        Node tail = dummy;
        while (a != null && b != null) {
            if (a.value <= b.value) {
                tail.next = a;
                a = a.next;
            } else {
                tail.next = b;
                b = b.next;
            }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return dummy.next;
    }

    // Stable sort preserves the original order within each source and A-before-B ties.
    public static Node baseline(Node a, Node b) {
        ArrayList<Node> nodes = new ArrayList<>();
        for (Node p = a; p != null; p = p.next) nodes.add(p);
        for (Node p = b; p != null; p = p.next) nodes.add(p);
        nodes.sort(Comparator.comparingInt(node -> node.value));
        for (int i = 0; i < nodes.size(); i++)
            nodes.get(i).next = i + 1 < nodes.size() ? nodes.get(i + 1) : null;
        return nodes.isEmpty() ? null : nodes.get(0);
    }
}

Read the meaningful blocks

Sentinel and tail

dummy provides a predecessor even for the first output node. Its arbitrary value is never compared, so Integer.MIN_VALUE needs no special case.

Choose before advancing

tail.next=a; a=a.next preserves the original successor before tail advances. The B branch is symmetric. Only one source advances per iteration.

Finish without scanning the suffix

tail.next = a != null ? a : b handles empty, exhausted, and one-sided cases in one assignment. The returned node is an original input head or null.

Complexity

For n and m input nodes, optimized merge takes O(n+m) worst-case time, O(1) auxiliary references, and one temporary Node allocation. If one list starts empty, attaching the other takes O(1) time. No new output nodes are allocated.

The stable-sort baseline uses O(n+m) auxiliary references (including sorting work space) and O((n+m) log(n+m)) comparison time as an upper bound. A recursive merge consumes O(n+m) stack space in the worst case and may overflow on 200,000 nodes.

Exact-state walkthroughs

Reveal normal and boundary traces

Interleaved identities and equal-value ties

Input: {"a":[1,3,3],"b":[2,3,4]} · Outcome / chain identities: ["A0","B0","A1","A2","B1","B2"]

Step 1 of 15: Initialize the temporary predecessor; no original node has been consumed.

The selected sequence ends at tail. A and B root disjoint sorted original suffixes.

Stable merge — original identities and current links

A cursor: A0 · B cursor: B0 · tail: dummy. Temporary dummy.next: null.

A0: 1next → A1a
A1: 3next → A2
A2: 3next → null
B0: 2next → B1b
B1: 3next → B2
B2: 4next → null

Selected prefix ending at tail: (empty). Its tail may still point into an unconsumed suffix. Cards stay in original source order; follow the named next references for the current chain. The dummy is outside the output.

State after this step
Variable	Value
nodes	`[{"id":"A0","value":1,"next":"A1"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"B1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]`
a	`"A0"`
b	`"B0"`
tail	`"dummy"`
dummyNext	`null`
selected	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Comparator;
 3 
 4 public final class Solution {
 5     public static final class Node {
 6         public final int value;
 7         public Node next;
 8         public Node(int value) { this.value = value; }
 9     }
10 
11     // Inputs must be sorted, acyclic, and node-disjoint. Reuses their nodes.
12     public static Node merge(Node a, Node b) {
13         Node dummy = new Node(0);
14         Node tail = dummy;
15         while (a != null && b != null) {
16             if (a.value <= b.value) {
17                 tail.next = a;
18                 a = a.next;
19             } else {
20                 tail.next = b;
21                 b = b.next;
22             }
23             tail = tail.next;
24         }
25         tail.next = a != null ? a : b;
26         return dummy.next;
27     }
28 
29     // Stable sort preserves the original order within each source and A-before-B ties.
30     public static Node baseline(Node a, Node b) {
31         ArrayList<Node> nodes = new ArrayList<>();
32         for (Node p = a; p != null; p = p.next) nodes.add(p);
33         for (Node p = b; p != null; p = p.next) nodes.add(p);
34         nodes.sort(Comparator.comparingInt(node -> node.value));
35         for (int i = 0; i < nodes.size(); i++)
36             nodes.get(i).next = i + 1 < nodes.size() ? nodes.get(i + 1) : null;
37         return nodes.isEmpty() ? null : nodes.get(0);
38     }
39 }
40

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

Read the full static trace

Initialize the temporary predecessor; no original node has been consumed.
The selected sequence ends at tail. A and B root disjoint sorted original suffixes.
nodes
[{"id":"A0","value":1,"next":"A1"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"B1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A0"
b
"B0"
tail
"dummy"
dummyNext
null
selected
[]
phase
"initial"
Link A0 from tail; choose A on equal values.
Only the old tail link is written. The chosen node still retains its original successor; the source cursor has not moved yet.
nodes
[{"id":"A0","value":1,"next":"A1"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"B1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A0"
b
"B0"
tail
"dummy"
dummyNext
"A0"
selected
[]
phase
"link"
source
"a"
chosen
"A0"
Save progress by advancing only source A.
Reading the chosen node successor preserves the rest of its source before later iterations can rewrite that edge.
nodes
[{"id":"A0","value":1,"next":"A1"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"B1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A1"
b
"B0"
tail
"dummy"
dummyNext
"A0"
selected
[]
phase
"source"
source
"a"
chosen
"A0"
Advance tail to the selected identity.
Selected identities are the stable sorted merge of consumed source prefixes. The final tail link may still lead into an unconsumed suffix.
nodes
[{"id":"A0","value":1,"next":"A1"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"B1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A1"
b
"B0"
tail
"A0"
dummyNext
"A0"
selected
["A0"]
phase
"tail"
source
"a"
chosen
"A0"
Link B0 from tail; choose A on equal values.
Only the old tail link is written. The chosen node still retains its original successor; the source cursor has not moved yet.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"B1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A1"
b
"B0"
tail
"A0"
dummyNext
"A0"
selected
["A0"]
phase
"link"
source
"b"
chosen
"B0"
Save progress by advancing only source B.
Reading the chosen node successor preserves the rest of its source before later iterations can rewrite that edge.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"B1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A1"
b
"B1"
tail
"A0"
dummyNext
"A0"
selected
["A0"]
phase
"source"
source
"b"
chosen
"B0"
Advance tail to the selected identity.
Selected identities are the stable sorted merge of consumed source prefixes. The final tail link may still lead into an unconsumed suffix.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"B1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A1"
b
"B1"
tail
"B0"
dummyNext
"A0"
selected
["A0","B0"]
phase
"tail"
source
"b"
chosen
"B0"
Link A1 from tail; choose A on equal values.
Only the old tail link is written. The chosen node still retains its original successor; the source cursor has not moved yet.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"A1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A1"
b
"B1"
tail
"B0"
dummyNext
"A0"
selected
["A0","B0"]
phase
"link"
source
"a"
chosen
"A1"
Save progress by advancing only source A.
Reading the chosen node successor preserves the rest of its source before later iterations can rewrite that edge.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"A1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A2"
b
"B1"
tail
"B0"
dummyNext
"A0"
selected
["A0","B0"]
phase
"source"
source
"a"
chosen
"A1"
Advance tail to the selected identity.
Selected identities are the stable sorted merge of consumed source prefixes. The final tail link may still lead into an unconsumed suffix.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"A1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A2"
b
"B1"
tail
"A1"
dummyNext
"A0"
selected
["A0","B0","A1"]
phase
"tail"
source
"a"
chosen
"A1"
Link A2 from tail; choose A on equal values.
Only the old tail link is written. The chosen node still retains its original successor; the source cursor has not moved yet.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"A1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
"A2"
b
"B1"
tail
"A1"
dummyNext
"A0"
selected
["A0","B0","A1"]
phase
"link"
source
"a"
chosen
"A2"
Save progress by advancing only source A.
Reading the chosen node successor preserves the rest of its source before later iterations can rewrite that edge.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"A1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
null
b
"B1"
tail
"A1"
dummyNext
"A0"
selected
["A0","B0","A1"]
phase
"source"
source
"a"
chosen
"A2"
Advance tail to the selected identity.
Selected identities are the stable sorted merge of consumed source prefixes. The final tail link may still lead into an unconsumed suffix.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":null},{"id":"B0","value":2,"next":"A1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
null
b
"B1"
tail
"A2"
dummyNext
"A0"
selected
["A0","B0","A1","A2"]
phase
"tail"
source
"a"
chosen
"A2"
Attach the untouched remaining chain once.
Every remaining value belongs after the selected prefix. No suffix node needs to be copied or individually scanned by the Java algorithm.
nodes
[{"id":"A0","value":1,"next":"B0"},{"id":"A1","value":3,"next":"A2"},{"id":"A2","value":3,"next":"B1"},{"id":"B0","value":2,"next":"A1"},{"id":"B1","value":3,"next":"B2"},{"id":"B2","value":4,"next":null}]
a
null
b
"B1"
tail
"A2"
dummyNext
"A0"
selected
["A0","B0","A1","A2"]
phase
"suffix"
remaining
"B1"
Return the contract result as an ordered view of original node identities.
These labels describe the returned chain; Java returns its original head reference. The temporary dummy is excluded.
result
["A0","B0","A1","A2","B1","B2"]

Empty A attaches original B

Input: {"a":[],"b":[7,9]} · Outcome / chain identities: ["B0","B1"]

Step 1 of 3: Initialize the temporary predecessor; no original node has been consumed.

The selected sequence ends at tail. A and B root disjoint sorted original suffixes.

Stable merge — original identities and current links

A cursor: null · B cursor: B0 · tail: dummy. Temporary dummy.next: null.

B0: 7next → B1b
B1: 9next → null

State after this step
Variable	Value
nodes	`[{"id":"B0","value":7,"next":"B1"},{"id":"B1","value":9,"next":null}]`
a	`null`
b	`"B0"`
tail	`"dummy"`
dummyNext	`null`
selected	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Comparator;
 3 
 4 public final class Solution {
 5     public static final class Node {
 6         public final int value;
 7         public Node next;
 8         public Node(int value) { this.value = value; }
 9     }
10 
11     // Inputs must be sorted, acyclic, and node-disjoint. Reuses their nodes.
12     public static Node merge(Node a, Node b) {
13         Node dummy = new Node(0);
14         Node tail = dummy;
15         while (a != null && b != null) {
16             if (a.value <= b.value) {
17                 tail.next = a;
18                 a = a.next;
19             } else {
20                 tail.next = b;
21                 b = b.next;
22             }
23             tail = tail.next;
24         }
25         tail.next = a != null ? a : b;
26         return dummy.next;
27     }
28 
29     // Stable sort preserves the original order within each source and A-before-B ties.
30     public static Node baseline(Node a, Node b) {
31         ArrayList<Node> nodes = new ArrayList<>();
32         for (Node p = a; p != null; p = p.next) nodes.add(p);
33         for (Node p = b; p != null; p = p.next) nodes.add(p);
34         nodes.sort(Comparator.comparingInt(node -> node.value));
35         for (int i = 0; i < nodes.size(); i++)
36             nodes.get(i).next = i + 1 < nodes.size() ? nodes.get(i + 1) : null;
37         return nodes.isEmpty() ? null : nodes.get(0);
38     }
39 }
40

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

Read the full static trace

Initialize the temporary predecessor; no original node has been consumed.
The selected sequence ends at tail. A and B root disjoint sorted original suffixes.
nodes
[{"id":"B0","value":7,"next":"B1"},{"id":"B1","value":9,"next":null}]
a
null
b
"B0"
tail
"dummy"
dummyNext
null
selected
[]
phase
"initial"
Attach the untouched remaining chain once.
Every remaining value belongs after the selected prefix. No suffix node needs to be copied or individually scanned by the Java algorithm.
nodes
[{"id":"B0","value":7,"next":"B1"},{"id":"B1","value":9,"next":null}]
a
null
b
"B0"
tail
"dummy"
dummyNext
"B0"
selected
[]
phase
"suffix"
remaining
"B0"
Return the contract result as an ordered view of original node identities.
These labels describe the returned chain; Java returns its original head reference. The temporary dummy is excluded.
result
["B0","B1"]

Test the contract

Input: A:null, B:null
Output: null
No returned sentinel.
Input: A:null, B:B0(0)
Output: B0
Original identity reused.
Input: A:A0(2)→A1(2), B:B0(2)→B1(2)
Output: A0,A1,B0,B1
Tie policy across and within lists.
Input: A:[MIN,MAX], B:[MIN,0,MAX]
Output: A0,B0,B1,A1,B2
Extreme values expose subtraction comparators.
Input: A:[1,3,5], B:[2,4,6]
Output: A0,B0,A1,B1,A2,B2
Repeated rewiring and suffix attachment.

Common mistakes and counterexamples

Accept shared-tail inputs silently

Counterexample: If a and b are the same single node X, selecting X then attaching b sets X.next=X, creating a cycle.

State the disjointness precondition. To support sharing, detect the common suffix and merge only disjoint prefixes under a separately defined identity policy.

Use < despite promising A-first ties

Counterexample: A0(2), B0(2) would produce B0 before A0.

Use <= and test exact reference order, including several consecutive equal nodes.

Return dummy or the original A head

Counterexample: A:null, B:B0 returns the wrong head or an extra sentinel.

Return dummy.next; test both empty and each one-sided case.

Test only sorted values

Counterexample: A fresh copied list or dropped duplicate occurrence could appear sorted.

Compare every output reference against an independently stable-sorted reference list and require null immediately after the expected count.

Follow-ups

What if the two inputs share a tail?

First decide whether each physical node appears once or each logical occurrence is copied. For one-identity output, find the shared entry, merge the disjoint prefixes, and append the shared suffix once; the current unchecked implementation must not be used.

Merge k sorted linked lists.

Use a heap of current heads, O(N log k) time and O(k) heap entries, or pairwise divide-and-conquer. Specify tie order using source index and stable source position; require disjoint ownership for destructive merging.

What if callers retain the original lists?

Use newly allocated output nodes and leave every original edge unchanged. This changes the identity contract and adds O(n+m) output allocation; persistent suffix sharing needs an explicit immutability/alias policy.

Related foundations

Linked lists: identity, reachability, and update order

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Familiar problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.