Loading…

mediumLinked ListsFrequently asked

Find the Merge Point of Two Linked Lists

Q: How do you solve Find the Merge Point of Two Linked Lists using the Hash Set — Remember One List's Nodes (Baseline) approach?

When to use it: Say this first as the obvious, easy-to-verify answer, then improve the space with the two-pointer trick. We record the identity of every node in one list, then scan the other for the first match. **Why store nodes, not values.** Intersection is defined by identity, so the set must hold node *references*. If we stored values, two distinct nodes holding the same number would falsely register as a merge. In Java that's an `IdentityHashMap`-style set or just a `HashSet ` (default identity hashCode); in Python, object `id` semantics make `set()` of nodes do the right thing. **Why the first hit in B is the answer.** Because a singly linked list can't split, the moment list B steps onto a node that belongs to A, every following node is shared too. So the *first* node of B found in the set is precisely the merge point. **Why we still want better.** This is correct and trivially explainable, but it costs O(n) memory. Interviewers usually push for O(1) space, which the two-pointer switch achieves. Lead with this to show the idea, then optimize. Time complexity: O(n + m). Space complexity: O(n).

Q: How do you solve Find the Merge Point of Two Linked Lists using the Two Pointers — Switch Heads at the End (Optimal) approach?

When to use it: The O(1)-space answer interviewers want. Phrase it as 'cancel the length difference by swapping lists', not just 'two pointers'. We run one pointer down each list; whenever a pointer runs off the end, we send it to the *other* list's head. After the swap the pointers are length-aligned and meet at the join. **The length problem, and the fix.** If list A is shorter, a pointer at A's head and one at B's head are misaligned: when both step together, A's pointer reaches the shared tail 'too early'. The switch fixes this without measuring anything. Pointer `a` walks `lenA`, then crosses to B and walks `lenB_before_merge` to reach the join — total `lenA + (lenB_before)`. Pointer `b` walks `lenB`, crosses to A, walks `lenA_before` — total `lenB + (lenA_before)`. Since `lenA = lenA_before + shared` and `lenB = lenB_before + shared`, both totals equal `lenA_before + lenB_before + shared` = `lenA + lenB_before` = `lenB + lenA_before`. Equal distances → they land on the intersection together. **Compare by identity.** The loop condition is `a != b` comparing node *references*. When they point at the same physical node, that node is the merge point. Never compare `a.val == b.val` — distinct nodes can share a value. **Why the no-intersection case terminates.** If the lists never merge, each pointer walks `lenA + lenB` and then becomes null. Crucially, both become null on the *same* step (they've each traveled `lenA + lenB`), so `a == b` holds with both being null and the loop exits returning null — no infinite loop. **Why redirect on the step after null, not skip null.** The trick relies on each pointer 'spending' exactly one step at the boundary. Reading `a = a.next if a else headB` means when `a` is null we send it to `headB`; the symmetric null arrivals are what guarantee the equal-distance meeting (including the both-null exit). Time complexity: O(n + m). Space complexity: O(1).

Linked List · 16 of 24 · 9 min

You are given the heads of two singly linked lists, headA and headB. The two lists may merge at some node — after which they share all subsequent nodes (a Y-shape).

Return the node at which the two lists intersect. If they do not intersect, return null.

Intersection is by node identity, not value. The lists are acyclic and must not be modified.

In plain English

If two singly linked lists merge, they can never split again — once they share a node they share every node after it (each node has exactly one next). So the intersection is the first shared node. The challenge is the lists can have different lengths before the join, so naive aligned walking from both heads misses it.

Examples

Example 1

Input: A = [4, 1, 8, 4, 5], B = [5, 6, 1, 8, 4, 5], merge at node with val 8
Output: node with val 8
Note: A has 2 nodes before the join, B has 3. The shared tail 8 → 4 → 5 starts at the node holding 8.

Example 2

Input: A = [2, 6, 4], B = [1, 5], no shared node
Output: null
Note: The lists never merge; both pointers eventually become null on the same step.

Example 3

Input: A = [1, 9, 1, 2, 4], B = [3, 2, 4], merge at node with val 2
Output: node with val 2
Note: Shared tail 2 → 4; A has 3 nodes before it, B has 1.

Constraints

0 ≤ lenA, lenB ≤ 3·10⁴
1 ≤ Node.val ≤ 10⁵
If the lists intersect, they share a common suffix (no diverging after the merge)
The lists are acyclic; do not modify them

Clarifying questions4First question: Is intersection defined by node identity or by equal values?Explore questions

Q1.Is intersection defined by node identity or by equal values?
By identity — the same physical node. Two different nodes with the same value are not an intersection, so I compare references, not vals.
Q2.Can the two lists have different lengths before merging?
Yes — that's the whole difficulty. The pre-merge tails can differ in length, so I need to cancel that difference before comparing.
Q3.Am I allowed to modify the lists?
No. I'll only read next pointers; I won't reverse, splice, or add cycles.
Q4.What if one or both lists are empty?
If either head is null there can be no intersection, so the answer is null — and the algorithms handle it naturally.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Two pointers, one per list. When a pointer hits the end, redirect it to the *other* list's head. After at most one switch each, both pointers have walked lenA + lenB nodes and meet exactly at the intersection node — or both reach null together if the lists never merge. O(n + m) time, O(1) space, no length math needed.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you compare nodes by reference rather than value, and whether you can equalize two different list lengths — either by switching heads or by advancing the longer list first — without brute-forcing all pairs.

Where candidates slip

Comparing a.val == b.val instead of a == b (a node identity), or building the length-difference solution off-by-one so the pointers never align.

How to stand out

Lead with the switching-heads two-pointer for O(1) space, explain *why* both pointers walk lenA + lenB, and mention the hash-set and length-difference alternatives as trade-offs.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Set — Remember One List's Nodes (Baseline)	`O(n + m)`	`O(n)`	Say this first as the obvious, easy-to-verify answer, then improve the space with the two-pointer trick.	Read
2	Two Pointers — Switch Heads at the End (Optimal)Optimal	`O(n + m)`	`O(1)`	The O(1)-space answer interviewers want. Phrase it as 'cancel the length difference by swapping lists', not just 'two pointers'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind merge point of two listsO(1) space required?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Hash Set — Remember One List's Nodes (Baseline)

TimeO(n + m)SpaceO(n)

Say this first as the obvious, easy-to-verify answer, then improve the space with the two-pointer trick.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you wrote down every node of list A, how would you then test each node of list B?

2Hint 2Explore hint

Store node references (not values) in a hash set as you walk A.

3Hint 3Explore hint

Walk B and return the first node already in the set — that's the first shared node, the intersection.

A · Core idea

We record the identity of every node in one list, then scan the other for the first match.

Why store nodes, not values. Intersection is defined by identity, so the set must hold node references. If we stored values, two distinct nodes holding the same number would falsely register as a merge. In Java that's an IdentityHashMap-style set or just a HashSet (default identity hashCode); in Python, object id semantics make set() of nodes do the right thing.

Why the first hit in B is the answer. Because a singly linked list can't split, the moment list B steps onto a node that belongs to A, every following node is shared too. So the first node of B found in the set is precisely the merge point.

Why we still want better. This is correct and trivially explainable, but it costs O(n) memory. Interviewers usually push for O(1) space, which the two-pointer switch achieves. Lead with this to show the idea, then optimize.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [4, 1, 8], B = [6, 8], merge at node 8

Hash-map state

scan A

lookup n8

ValueIndex / state

n4→ •

n1→ •

n8→ •

Continue scanning

insert n4, n1, n8

Final resultnode with val 8

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the full code

solution.javaJava

Hash Set — Remember One List's Nodes (Baseline) — reference

4 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
10
    // Stores node references — identity, not value, defines intersection.
11
    Set<ListNode> seen = new HashSet<>();
12
    for (ListNode a = headA; a != null; a = a.next) {
13
        // Record every node of list A.
14
        seen.add(a);
15
    }
16
    for (ListNode b = headB; b != null; b = b.next) {
17
        // First node of B that is in the set is the merge point.
18
        if (seen.contains(b)) {
19
            return b;
20
        }
21
    }
22
    // B exhausted with no match — the lists don't intersect.
23
    return null;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n + m) timeO(n) spaceOpen the invariant and proofExplore the proof

Membership testing turns 'do these paths share a node?' into 'have I seen this exact node before?' — the same remember-and-probe shape as Two Sum, applied to references instead of values.

ComplexityO(n + m) time, O(n) space — One pass over A to fill the set (n inserts), one pass over B to probe (m lookups), each O(1) average → O(n + m) time. The set holds up to n node references → O(n) space.

E · Edge cases and pitfalls5A = [], B = [1] — Set is empty; probing B finds nothing → null.Explore edge cases

Edge cases handled

A = [], B = [1]Set is empty; probing B finds nothing → null.
A = B (same head)Every node of B is in the set; first node returned is the shared head.

Pitfalls

Storing values instead of node references — two equal values falsely look like an intersection.
Probing A against B but inserting B (works, but be consistent) — pick one list to record.
Assuming O(1) space — this is O(n), which is exactly what the two-pointer version fixes.

03.2

Approach 2 of 2 · Optimal

Two Pointers — Switch Heads at the End (Optimal)

TimeO(n + m)SpaceO(1)

The O(1)-space answer interviewers want. Phrase it as 'cancel the length difference by swapping lists', not just 'two pointers'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The only thing stopping a simple side-by-side walk is that the two lists have different lengths before the join. How could you make both pointers travel the *same* total distance?

2Hint 2Explore hint

Let each pointer, on reaching the end of its list, jump to the head of the OTHER list. How far has each pointer traveled when they meet?

3Hint 3Explore hint

After the switch, pointer A walks lenA + lenB and pointer B walks lenB + lenA — equal totals — so they arrive at the intersection on the same step. If there's no intersection, they hit null together.

A · Core idea

We run one pointer down each list; whenever a pointer runs off the end, we send it to the other list's head. After the swap the pointers are length-aligned and meet at the join.

The length problem, and the fix. If list A is shorter, a pointer at A's head and one at B's head are misaligned: when both step together, A's pointer reaches the shared tail 'too early'. The switch fixes this without measuring anything. Pointer a walks lenA, then crosses to B and walks lenB_before_merge to reach the join — total lenA + (lenB_before). Pointer b walks lenB, crosses to A, walks lenA_before — total lenB + (lenA_before). Since lenA = lenA_before + shared and lenB = lenB_before + shared, both totals equal lenA_before + lenB_before + shared = lenA + lenB_before = lenB + lenA_before. Equal distances → they land on the intersection together.

Compare by identity. The loop condition is a != b comparing node references. When they point at the same physical node, that node is the merge point. Never compare a.val == b.val — distinct nodes can share a value.

Why the no-intersection case terminates. If the lists never merge, each pointer walks lenA + lenB and then becomes null. Crucially, both become null on the same step (they've each traveled lenA + lenB), so a == b holds with both being null and the loop exits returning null — no infinite loop.

Why redirect on the step after null, not skip null. The trick relies on each pointer 'spending' exactly one step at the boundary. Reading a = a.next if a else headB means when a is null we send it to headB; the symmetric null arrivals are what guarantee the equal-distance meeting (including the both-null exit).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [4, 1, 8], B = [6, 1, 8], merge at node 8 (shared tail of length 1)

Interactive diagram

Why switching heads aligns the pointers

start

Active call / nodeSupporting contextReturned stateNot active

Both pointers traverse lenA + lenB nodes, so they arrive at the merge node on the same step.

Final resultnode with val 8 (the shared node)

C · Code with teaching comments

solution.javaJava

Two Pointers — Switch Heads at the End (Optimal) — optimal

5 teaching notes

1
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
2
    // An empty list can't intersect anything.
3
    if (headA == null || headB == null) return null;
4
    ListNode a = headA;
5
    ListNode b = headB;
6
    // Compare by reference (identity), never by value — that's the named trap.
7
    while (a != b) {
8
        // When a hits the end, jump to the OTHER list's head to cancel the length gap.
9
        a = (a == null) ? headB : a.next;
10
        // Symmetric switch for b; equal total distances make them meet at the join.
11
        b = (b == null) ? headA : b.next;
12
    }
13
    // a == b: either the intersection node, or both null (no intersection).
14
    return a;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n + m) timeO(1) spaceOpen the invariant and proofExplore the proof

Switching heads is a way to make two unequal lengths equal for free — no counting, no second pass to measure. The named trap is comparing values instead of node identity; the second trap is sending a null pointer back to its own head instead of the other's, which breaks the length cancellation.

ComplexityO(n + m) time, O(1) space — Each pointer traverses at most lenA + lenB nodes before meeting or both reaching null → O(n + m) time. Only two pointers are used → O(1) space.

E · Edge cases and pitfalls7A = [2, 6, 4], B = [1, 5] (no merge) — Each pointer walks 5 nodes then both become null on the same step → a == b == null → return null.Explore edge cases

Edge cases handled

A = [2, 6, 4], B = [1, 5] (no merge)Each pointer walks 5 nodes then both become null on the same step → a == b == null → return null.
Same length, merge at heada and b are equal from the first comparison (no switch needed) → return the shared head.
A = [3], B = [3] distinct nodes, no mergeEqual values but different nodes; pointers switch and both reach null together → null.

Pitfalls

Comparing a.val == b.val instead of node identity — false matches on repeated values.
On reaching null, jumping to the SAME list's head instead of the other — the length difference never cancels and you loop forever.
Skipping null instead of spending one step on it — breaks the equal-distance guarantee, including the both-null exit.
Assuming the lists are cyclic — this method requires acyclic lists; detect/remove cycles first.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode a = headA; ListNode b = headB; while (a != b) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Comparing values instead of identity

Intersection means the same physical node. Two different nodes can hold equal values (e.g. both 8), so a value comparison reports a false merge before the real one.

Explore the code comparison

Don't write this

while (a != null && b != null) {
    if (a.val == b.val) return a;  // false positive on repeated values
    a = a.next; b = b.next;
}

Write this instead

while (a != b) {  // reference comparison
    a = (a == null) ? headB : a.next;
    b = (b == null) ? headA : b.next;
}
return a;

Switching to the wrong head

The length cancellation only works if a finished pointer crosses into the OTHER list. Sending it back to its own head keeps the same length and the pointers never align — an infinite loop on intersecting lists.

Explore the code comparison

Don't write this

a = headA if a is None else a.next   # wrong: back to own head
b = headB if b is None else b.next

Write this instead

a = headB if a is None else a.next   # cross to the other list
b = headA if b is None else b.next

Off-by-one in the length-difference method

An alternative is to advance the longer list by |lenA − lenB| first, then walk together. Miscounting the difference (or which list is longer) shifts the alignment so the pointers pass the intersection without meeting.

Explore the code comparison

Don't write this

diff = lenA - lenB
for _ in range(diff):   # negative when B is longer → no-op, misaligned
    a = a.next

Write this instead

diff = abs(lenA - lenB)
longer = a if lenA > lenB else b
for _ in range(diff):
    longer = longer.next

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Switching-heads two pointers (equalize path lengths by swapping lists)

Code pattern to memorize

a, b = headA, headB
while a is not b:
    a = a.next if a else headB
    b = b.next if b else headA
return a   # the intersection node, or null

Rules to remember

1Compare nodes by identity (a == b / a is b), never by value — two equal values aren't the same node.
2When a pointer hits null, redirect it to the other list's head — not its own — to cancel the length difference.
3Redirect to the head on the step after reaching null, so each pointer walks exactly lenA + lenB and they align.
4If the lists don't intersect, both pointers become null on the same step and a is b (both null) ends the loop → return null.
5Do not mutate the lists; this is a read-only traversal (no cycles are created).

Use this pattern when

Find where two singly linked lists join into a shared tail (Y-shape)
Detect a shared suffix without knowing the lengths in advance
Any 'two paths converge' problem on pointer-based structures
When O(1) extra space is required and you can't use a hash set

Choose another pattern when

The lists may form a cycle → handle the cycle first (Floyd), this assumes acyclic Y-shape
You can mutate freely and want the simplest code → a hash set of one list's nodes is more obvious
You only need whether they intersect, not the node → still works, but a set answers it too
Nodes can be compared by value uniquely → still compare by reference; values may repeat

Interview takeaway

The switching-heads trick equalizes two unequal path lengths without ever measuring them: after each pointer crosses into the other list, both have lenA + lenB to walk, so they land on the join together. It's the cleanest O(1)-space answer and the same length-alignment idea behind many two-pointer problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTwo-pointer length alignment via head switching: equalize two unequal path lengths without measuring them, so the pointers converge at the shared node. The same convergence idea drives cycle-entry detection and any 'two traversals must meet' problem.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Delete a Node at a Given Position in a Linked List

Continue · Next problem

Insert a Node at the Head of a Linked List

mediumLinked ListsFrequently asked

Find the Merge Point of Two Linked Lists

Linked List · 16 of 24 · 9 min

You are given the heads of two singly linked lists, headA and headB. The two lists may merge at some node — after which they share all subsequent nodes (a Y-shape).

Return the node at which the two lists intersect. If they do not intersect, return null.

Intersection is by node identity, not value. The lists are acyclic and must not be modified.

In plain English

Examples

Example 1

Input: A = [4, 1, 8, 4, 5], B = [5, 6, 1, 8, 4, 5], merge at node with val 8
Output: node with val 8
Note: A has 2 nodes before the join, B has 3. The shared tail 8 → 4 → 5 starts at the node holding 8.

Example 2

Input: A = [2, 6, 4], B = [1, 5], no shared node
Output: null
Note: The lists never merge; both pointers eventually become null on the same step.

Example 3

Input: A = [1, 9, 1, 2, 4], B = [3, 2, 4], merge at node with val 2
Output: node with val 2
Note: Shared tail 2 → 4; A has 3 nodes before it, B has 1.

Constraints

0 ≤ lenA, lenB ≤ 3·10⁴
1 ≤ Node.val ≤ 10⁵
If the lists intersect, they share a common suffix (no diverging after the merge)
The lists are acyclic; do not modify them

Clarifying questions4First question: Is intersection defined by node identity or by equal values?Explore questions

Q1.Is intersection defined by node identity or by equal values?
By identity — the same physical node. Two different nodes with the same value are not an intersection, so I compare references, not vals.
Q2.Can the two lists have different lengths before merging?
Yes — that's the whole difficulty. The pre-merge tails can differ in length, so I need to cancel that difference before comparing.
Q3.Am I allowed to modify the lists?
No. I'll only read next pointers; I won't reverse, splice, or add cycles.
Q4.What if one or both lists are empty?
If either head is null there can be no intersection, so the answer is null — and the algorithms handle it naturally.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Comparing a.val == b.val instead of a == b (a node identity), or building the length-difference solution off-by-one so the pointers never align.

How to stand out

Lead with the switching-heads two-pointer for O(1) space, explain *why* both pointers walk lenA + lenB, and mention the hash-set and length-difference alternatives as trade-offs.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Set — Remember One List's Nodes (Baseline)	`O(n + m)`	`O(n)`	Say this first as the obvious, easy-to-verify answer, then improve the space with the two-pointer trick.	Read
2	Two Pointers — Switch Heads at the End (Optimal)Optimal	`O(n + m)`	`O(1)`	The O(1)-space answer interviewers want. Phrase it as 'cancel the length difference by swapping lists', not just 'two pointers'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Hash Set — Remember One List's Nodes (Baseline)

TimeO(n + m)SpaceO(n)

Say this first as the obvious, easy-to-verify answer, then improve the space with the two-pointer trick.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you wrote down every node of list A, how would you then test each node of list B?

2Hint 2Explore hint

Store node references (not values) in a hash set as you walk A.

3Hint 3Explore hint

Walk B and return the first node already in the set — that's the first shared node, the intersection.

A · Core idea

We record the identity of every node in one list, then scan the other for the first match.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [4, 1, 8], B = [6, 8], merge at node 8

Hash-map state

scan A

lookup n8

ValueIndex / state

n4→ •

n1→ •

n8→ •

Continue scanning

insert n4, n1, n8

Final resultnode with val 8

C · Code with teaching comments

Reference implementation previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the full code

solution.javaJava

Hash Set — Remember One List's Nodes (Baseline) — reference

4 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
10
    // Stores node references — identity, not value, defines intersection.
11
    Set<ListNode> seen = new HashSet<>();
12
    for (ListNode a = headA; a != null; a = a.next) {
13
        // Record every node of list A.
14
        seen.add(a);
15
    }
16
    for (ListNode b = headB; b != null; b = b.next) {
17
        // First node of B that is in the set is the merge point.
18
        if (seen.contains(b)) {
19
            return b;
20
        }
21
    }
22
    // B exhausted with no match — the lists don't intersect.
23
    return null;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n + m) timeO(n) spaceOpen the invariant and proofExplore the proof

Membership testing turns 'do these paths share a node?' into 'have I seen this exact node before?' — the same remember-and-probe shape as Two Sum, applied to references instead of values.

E · Edge cases and pitfalls5A = [], B = [1] — Set is empty; probing B finds nothing → null.Explore edge cases

Edge cases handled

A = [], B = [1]Set is empty; probing B finds nothing → null.
A = B (same head)Every node of B is in the set; first node returned is the shared head.

Pitfalls

Storing values instead of node references — two equal values falsely look like an intersection.
Probing A against B but inserting B (works, but be consistent) — pick one list to record.
Assuming O(1) space — this is O(n), which is exactly what the two-pointer version fixes.

03.2

Approach 2 of 2 · Optimal

Two Pointers — Switch Heads at the End (Optimal)

TimeO(n + m)SpaceO(1)

The O(1)-space answer interviewers want. Phrase it as 'cancel the length difference by swapping lists', not just 'two pointers'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The only thing stopping a simple side-by-side walk is that the two lists have different lengths before the join. How could you make both pointers travel the *same* total distance?

2Hint 2Explore hint

Let each pointer, on reaching the end of its list, jump to the head of the OTHER list. How far has each pointer traveled when they meet?

3Hint 3Explore hint

A · Core idea

We run one pointer down each list; whenever a pointer runs off the end, we send it to the other list's head. After the swap the pointers are length-aligned and meet at the join.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [4, 1, 8], B = [6, 1, 8], merge at node 8 (shared tail of length 1)

Interactive diagram

Why switching heads aligns the pointers

start

Active call / nodeSupporting contextReturned stateNot active

Both pointers traverse lenA + lenB nodes, so they arrive at the merge node on the same step.

Final resultnode with val 8 (the shared node)

C · Code with teaching comments

solution.javaJava

Two Pointers — Switch Heads at the End (Optimal) — optimal

5 teaching notes

1
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
2
    // An empty list can't intersect anything.
3
    if (headA == null || headB == null) return null;
4
    ListNode a = headA;
5
    ListNode b = headB;
6
    // Compare by reference (identity), never by value — that's the named trap.
7
    while (a != b) {
8
        // When a hits the end, jump to the OTHER list's head to cancel the length gap.
9
        a = (a == null) ? headB : a.next;
10
        // Symmetric switch for b; equal total distances make them meet at the join.
11
        b = (b == null) ? headA : b.next;
12
    }
13
    // a == b: either the intersection node, or both null (no intersection).
14
    return a;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n + m) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n + m) time, O(1) space — Each pointer traverses at most lenA + lenB nodes before meeting or both reaching null → O(n + m) time. Only two pointers are used → O(1) space.

E · Edge cases and pitfalls7A = [2, 6, 4], B = [1, 5] (no merge) — Each pointer walks 5 nodes then both become null on the same step → a == b == null → return null.Explore edge cases

Edge cases handled

A = [2, 6, 4], B = [1, 5] (no merge)Each pointer walks 5 nodes then both become null on the same step → a == b == null → return null.
Same length, merge at heada and b are equal from the first comparison (no switch needed) → return the shared head.
A = [3], B = [3] distinct nodes, no mergeEqual values but different nodes; pointers switch and both reach null together → null.

Pitfalls

Comparing a.val == b.val instead of node identity — false matches on repeated values.
On reaching null, jumping to the SAME list's head instead of the other — the length difference never cancels and you loop forever.
Skipping null instead of spending one step on it — breaks the equal-distance guarantee, including the both-null exit.
Assuming the lists are cyclic — this method requires acyclic lists; detect/remove cycles first.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Comparing values instead of identity

Intersection means the same physical node. Two different nodes can hold equal values (e.g. both 8), so a value comparison reports a false merge before the real one.

Explore the code comparison

Don't write this

while (a != null && b != null) {
    if (a.val == b.val) return a;  // false positive on repeated values
    a = a.next; b = b.next;
}

Write this instead

while (a != b) {  // reference comparison
    a = (a == null) ? headB : a.next;
    b = (b == null) ? headA : b.next;
}
return a;

Switching to the wrong head

Explore the code comparison

Don't write this

a = headA if a is None else a.next   # wrong: back to own head
b = headB if b is None else b.next

Write this instead

a = headB if a is None else a.next   # cross to the other list
b = headA if b is None else b.next

Off-by-one in the length-difference method

Explore the code comparison

Don't write this

diff = lenA - lenB
for _ in range(diff):   # negative when B is longer → no-op, misaligned
    a = a.next

Write this instead

diff = abs(lenA - lenB)
longer = a if lenA > lenB else b
for _ in range(diff):
    longer = longer.next

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Switching-heads two pointers (equalize path lengths by swapping lists)

Code pattern to memorize

a, b = headA, headB
while a is not b:
    a = a.next if a else headB
    b = b.next if b else headA
return a   # the intersection node, or null

Rules to remember

1Compare nodes by identity (a == b / a is b), never by value — two equal values aren't the same node.
2When a pointer hits null, redirect it to the other list's head — not its own — to cancel the length difference.
3Redirect to the head on the step after reaching null, so each pointer walks exactly lenA + lenB and they align.
4If the lists don't intersect, both pointers become null on the same step and a is b (both null) ends the loop → return null.
5Do not mutate the lists; this is a read-only traversal (no cycles are created).

Use this pattern when

Find where two singly linked lists join into a shared tail (Y-shape)
Detect a shared suffix without knowing the lengths in advance
Any 'two paths converge' problem on pointer-based structures
When O(1) extra space is required and you can't use a hash set

Choose another pattern when

The lists may form a cycle → handle the cycle first (Floyd), this assumes acyclic Y-shape
You can mutate freely and want the simplest code → a hash set of one list's nodes is more obvious
You only need whether they intersect, not the node → still works, but a set answers it too
Nodes can be compared by value uniquely → still compare by reference; values may repeat

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Delete a Node at a Given Position in a Linked List

Continue · Next problem

Insert a Node at the Head of a Linked List