DSA-055 · FOCUSED PRACTICE

Intersection of Two Linked Lists

Core · Java 21 · Version 1 · editorial draft

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

Understand the problem

Return the first Node object shared by two acyclic singly linked lists, or null if there is no intersection. Preserve both input graphs. Intersection means object identity, not matching values.

Each input is null or roots a finite acyclic chain with at most 100,000 reachable nodes. Inputs may share a suffix, including the whole list. The graph is stable during the call; cyclic inputs are outside this contract.
Return the exact first shared object. Once two singly linked paths share a node, every subsequent node is shared because each next field has one value. Equal-valued separately allocated nodes are not intersections.
Neither method changes values or next fields. Same nonnull head returns that head immediately; two null inputs return null. No new output node is allocated.

Examples

Input: A0→A1→C0→C1; B0→C0→C1
Output: C0
The fixture must use the same C0 and C1 objects from both heads; copying equal values does not create sharing.
Input: A0(7)→A1(9); B0(7)→B1(9), all distinct
Output: null
The value sequences are equal but no reference is shared.
Input: Both heads are C0
Output: C0
Initial pointer identity already identifies the first shared object.

Before you start

Reference identity versus equal values
Acyclic singly linked lists and shared suffixes

Recognize the structure

A shared suffix can be reached after unequal private prefix lengths. Align the remaining distances to the common suffix, either using lengths or by letting each pointer traverse the other path. This is a read-only identity problem, distinct from destructive merging.

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

Self-review

I construct shared nodes once in the test fixture.I include the explicit null-switch transition in distance counts.I return an original reference and preserve every input edge.

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

Try before revealing

Hint 1

If lengths were known, you could align the remaining distances to the end.

Hint 2

Can each pointer traverse both lists so their total distances agree?

Hint 3

Advance normally, switch a null pointer to the other head, and stop when p==q, possibly at null.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Remember A identities and scan B

Insert all nodes reachable from A into an IdentityHashMap-backed set, then scan B until a stored reference is found. For A0→A1→C0 and B0→C0, the first B node in the set is C0. Because sharing persists as a suffix, this is the first common node for both lists. Expected time O(n+m), auxiliary storage O(n).

Improve the baseline

Switch after the explicit null state

Start p=a,q=b. On each iteration, replace a null p with b, otherwise use p.next; do the symmetric update for q. The explicit null state is part of this implementation’s timing.

Balance the two private prefixes

Write the inputs as private lengths aLen,bLen plus shared length c. With unequal total lengths, p reaches the entry after traversing its first entire list, one null-switch transition, and bLen nodes of the other prefix. q takes its first entire list, one switch, and aLen nodes. Both counts equal aLen+bLen+c+1.

Stop on reference equality, including null

If list lengths match and share a suffix, the pointers can meet at entry during the first pass. If disjoint, either they reach null together on the first equal-length pass or after both have traversed both lists. Return the shared reference or null; never compare values.

Why it is correct

No private-prefix intersection

A node in a private prefix cannot occur in the other chain by definition; a first meeting at a nonnull node must be in the shared suffix. With unequal private lengths, equal-step first-pass pointers cannot meet inside that suffix because their offsets differ.

Equalized arrival at entry

If lengths are equal, both pointers reach the entry after the same private-prefix length. If lengths differ, the second-path arrival counts aLen+bLen+c+1 are equal. Before that synchronized arrival, no earlier common identity is possible: on opposite paths their private-prefix positions are disjoint, and a residual offset in the shared suffix cannot disappear until path switching cancels it.

Absent sharing and termination

For disjoint chains, after n+m+1 transitions both pointers are null unless they already met null sooner. Empty inputs are included in the same rule. Each pointer follows at most two chains, so the loop terminates in O(n+m) time without changing any edge.

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.Collections;
import java.util.IdentityHashMap;
import java.util.Set;

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

    public static Node intersection(Node a, Node b) {
        Node p = a, q = b;
        while (p != q) {
            p = p == null ? b : p.next;
            q = q == null ? a : q.next;
        }
        return p;
    }

    public static Node baseline(Node a, Node b) {
        Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
        for (Node p = a; p != null; p = p.next) seen.add(p);
        for (Node q = b; q != null; q = q.next) if (seen.contains(q)) return q;
        return null;
    }
}

Read the meaningful blocks

Initialize at the two heads

The initial p==q case correctly handles identical heads and two empty lists.

Switch the null pointer, not its next

The update uses p==null ? b : p.next. A pointer at a tail first becomes null; a later iteration switches it. Short-circuit conditional evaluation prevents null dereference.

Return the common object

The loop condition p!=q is identity comparison. Returning p.value would lose absence information and the exact shared-node result.

Complexity

Time is O(n+m) and auxiliary space O(1); each pointer follows at most both input paths. The returned object belongs to the original graph and no input link is changed.

The identity-set baseline takes O(n+m) expected time and O(n) extra references. Length-difference alignment has the same O(1) auxiliary bound as switching but explicitly counts both paths first.

Exact-state walkthroughs

Reveal normal and boundary traces

Unequal prefixes converge on one shared suffix

Input: {"a":[4,1],"b":[9,2,3],"shared":[8,8]} · Result: "S0"

Step 1 of 10: Begin from the two original heads.

The S identities, when present, are one genuinely shared suffix, not equal-valued copies.

Intersection — distinct prefixes and one shared suffix

p: A0 · q: B0

A0: 4next → A1p
A1: 1next → S0
B0: 9next → B1q
B1: 2next → B2
B2: 3next → S0
S0: 8next → S1
S1: 8next → null

Cards remain in identity order; follow the named links for traversal order. S nodes are shared physical objects. Equal A/B values alone never establish intersection.

State after this step
Variable	Value
nodes	`[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]`
pointers	`{"p":"A0","q":"B0"}`
headA	`"A0"`
headB	`"B0"`
round	`0`

See the affected Java block

 1 import java.util.Collections;
 2 import java.util.IdentityHashMap;
 3 import java.util.Set;
 4 
 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 
12     public static Node intersection(Node a, Node b) {
13         Node p = a, q = b;
14         while (p != q) {
15             p = p == null ? b : p.next;
16             q = q == null ? a : q.next;
17         }
18         return p;
19     }
20 
21     public static Node baseline(Node a, Node b) {
22         Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
23         for (Node p = a; p != null; p = p.next) seen.add(p);
24         for (Node q = b; q != null; q = q.next) if (seen.contains(q)) return q;
25         return null;
26     }
27 }
28

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

Read the full static trace

Begin from the two original heads.
The S identities, when present, are one genuinely shared suffix, not equal-valued copies.
nodes
[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]
pointers
{"p":"A0","q":"B0"}
headA
"A0"
headB
"B0"
round
0
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]
pointers
{"p":"A1","q":"B1"}
headA
"A0"
headB
"B0"
round
1
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]
pointers
{"p":"S0","q":"B2"}
headA
"A0"
headB
"B0"
round
2
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]
pointers
{"p":"S1","q":"S0"}
headA
"A0"
headB
"B0"
round
3
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]
pointers
{"p":null,"q":"S1"}
headA
"A0"
headB
"B0"
round
4
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]
pointers
{"p":"B0","q":null}
headA
"A0"
headB
"B0"
round
5
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]
pointers
{"p":"B1","q":"A0"}
headA
"A0"
headB
"B0"
round
6
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]
pointers
{"p":"B2","q":"A1"}
headA
"A0"
headB
"B0"
round
7
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":4,"next":"A1"},{"id":"A1","value":1,"next":"S0"},{"id":"B0","value":9,"next":"B1"},{"id":"B1","value":2,"next":"B2"},{"id":"B2","value":3,"next":"S0"},{"id":"S0","value":8,"next":"S1"},{"id":"S1","value":8,"next":null}]
pointers
{"p":"S0","q":"S0"}
headA
"A0"
headB
"B0"
round
8
Return the documented outcome after all required mutation or restoration.
The result uses the declared value, identity, and ownership semantics.
result
"S0"

Equal values with disjoint identities

Input: {"a":[7,7],"b":[7,7],"shared":[]} · Result: null

Step 1 of 4: Begin from the two original heads.

The S identities, when present, are one genuinely shared suffix, not equal-valued copies.

Intersection — distinct prefixes and one shared suffix

p: A0 · q: B0

A0: 7next → A1p
A1: 7next → null
B0: 7next → B1q
B1: 7next → null

Cards remain in identity order; follow the named links for traversal order. S nodes are shared physical objects. Equal A/B values alone never establish intersection.

State after this step
Variable	Value
nodes	`[{"id":"A0","value":7,"next":"A1"},{"id":"A1","value":7,"next":null},{"id":"B0","value":7,"next":"B1"},{"id":"B1","value":7,"next":null}]`
pointers	`{"p":"A0","q":"B0"}`
headA	`"A0"`
headB	`"B0"`
round	`0`

See the affected Java block

 1 import java.util.Collections;
 2 import java.util.IdentityHashMap;
 3 import java.util.Set;
 4 
 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 
12     public static Node intersection(Node a, Node b) {
13         Node p = a, q = b;
14         while (p != q) {
15             p = p == null ? b : p.next;
16             q = q == null ? a : q.next;
17         }
18         return p;
19     }
20 
21     public static Node baseline(Node a, Node b) {
22         Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
23         for (Node p = a; p != null; p = p.next) seen.add(p);
24         for (Node q = b; q != null; q = q.next) if (seen.contains(q)) return q;
25         return null;
26     }
27 }
28

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

Read the full static trace

Begin from the two original heads.
The S identities, when present, are one genuinely shared suffix, not equal-valued copies.
nodes
[{"id":"A0","value":7,"next":"A1"},{"id":"A1","value":7,"next":null},{"id":"B0","value":7,"next":"B1"},{"id":"B1","value":7,"next":null}]
pointers
{"p":"A0","q":"B0"}
headA
"A0"
headB
"B0"
round
0
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":7,"next":"A1"},{"id":"A1","value":7,"next":null},{"id":"B0","value":7,"next":"B1"},{"id":"B1","value":7,"next":null}]
pointers
{"p":"A1","q":"B1"}
headA
"A0"
headB
"B0"
round
1
Advance or switch each null pointer to the other head.
Each switch includes the explicit null state. Traversing both paths cancels unequal private-prefix lengths.
nodes
[{"id":"A0","value":7,"next":"A1"},{"id":"A1","value":7,"next":null},{"id":"B0","value":7,"next":"B1"},{"id":"B1","value":7,"next":null}]
pointers
{"p":null,"q":null}
headA
"A0"
headB
"B0"
round
2
Return the documented outcome after all required mutation or restoration.
The result uses the declared value, identity, and ownership semantics.
result
null

Both heads already share the chain

Input: {"a":[],"b":[],"shared":[1,2]} · Result: "S0"

Step 1 of 2: Begin from the two original heads.

The S identities, when present, are one genuinely shared suffix, not equal-valued copies.

Intersection — distinct prefixes and one shared suffix

p: S0 · q: S0

S0: 1next → S1pq
S1: 2next → null

Cards remain in identity order; follow the named links for traversal order. S nodes are shared physical objects. Equal A/B values alone never establish intersection.

State after this step
Variable	Value
nodes	`[{"id":"S0","value":1,"next":"S1"},{"id":"S1","value":2,"next":null}]`
pointers	`{"p":"S0","q":"S0"}`
headA	`"S0"`
headB	`"S0"`
round	`0`

See the affected Java block

 1 import java.util.Collections;
 2 import java.util.IdentityHashMap;
 3 import java.util.Set;
 4 
 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 
12     public static Node intersection(Node a, Node b) {
13         Node p = a, q = b;
14         while (p != q) {
15             p = p == null ? b : p.next;
16             q = q == null ? a : q.next;
17         }
18         return p;
19     }
20 
21     public static Node baseline(Node a, Node b) {
22         Set<Node> seen = Collections.newSetFromMap(new IdentityHashMap<>());
23         for (Node p = a; p != null; p = p.next) seen.add(p);
24         for (Node q = b; q != null; q = q.next) if (seen.contains(q)) return q;
25         return null;
26     }
27 }
28

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

Read the full static trace

Begin from the two original heads.
The S identities, when present, are one genuinely shared suffix, not equal-valued copies.
nodes
[{"id":"S0","value":1,"next":"S1"},{"id":"S1","value":2,"next":null}]
pointers
{"p":"S0","q":"S0"}
headA
"S0"
headB
"S0"
round
0
Return the documented outcome after all required mutation or restoration.
The result uses the declared value, identity, and ownership semantics.
result
"S0"

Test the contract

Input: Both null
Output: null
Initial equality.
Input: A null, B nonempty
Output: null
Switching must terminate.
Input: Same head C0
Output: C0
Whole-chain sharing.
Input: Unequal private prefixes plus one shared node
Output: That shared reference
Actual alias fixture.
Input: Equal values, separately allocated nodes
Output: null
Identity rather than value.

Common mistakes and counterexamples

Build two equal-valued suffix copies

Counterexample: A fixture with separately allocated [8,9] suffixes has no intersection.

Create the shared chain once and attach both private tails to that exact object.

Compare values

Counterexample: Private A0(4) and B0(4) would falsely count as an intersection.

Use reference equality and all-equal disjoint tests.

Mutate a tail into a temporary cycle

Counterexample: Cycle-based tricks can damage shared callers and violate the no-write API.

Use head switching or length alignment, then check every original edge.

Apply switching to cyclic inputs

Counterexample: Two disjoint cycles need never reach null or meet.

Keep the acyclic precondition; cyclic intersection requires a separately defined algorithm and answer policy.

Follow-ups

Use length alignment instead.

Count both lengths, advance the longer head by their difference, then advance both until identity matches. The remaining suffix distances stay equal; no-write tests still apply.

Allow cycles in the inputs.

Find each cycle entry. Exactly one cyclic path cannot share a node with an acyclic path. With two cycles, determine whether they are the same cycle and define what result is acceptable when the two cycle entries differ.

Detect the first shared node across many heads.

Specify whether “shared” means by every head or any pair. Identity occurrence counts or graph metadata may be appropriate; the two-path distance-cancellation proof does not directly solve arbitrary many-head cases.

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. Standard problem names do not imply company-frequency or external platform-difficulty claims.