Definition
- Intersection – two singly linked lists share a common tail, forming a Y-shape; the intersection node is the first shared node by reference identity.
- Two-pointer switch – pointer A walks list A then list B; pointer B walks list B then list A; both traverse exactly
lenA + lenBnodes and meet at the intersection. - Length-difference – compute both lengths, advance the longer list's pointer by the difference, then walk both in lockstep comparing references.
- Termination – if no intersection, both pointers become
nullsimultaneously and the loop exits. - Complexity – O(n + m) time, O(1) space.
Two customers at the National Bank of India, Rajesh and Priya, each follow their own trail of linked statement nodes. At some point both trails merge into one shared trail of joint-account statements. To find where they merge, each walks their own trail and then continues onto the other person's trail. Because both cover the same total distance, they arrive at the merge point at the same moment.
Understanding the Concepts
What is the intersection of two linked lists?
Intersection means two singly linked lists literally share nodes from some point onward, forming a Y-shape. After the junction node, both lists follow the same chain. The problem asks for the first shared node by reference identity, not by value. Two nodes with the same value at different memory locations are not an intersection.
package com.bank.model;
import java.math.BigDecimal;
public class StatementNode {
public String accountId;
public BigDecimal amount;
public StatementNode next;
public StatementNode(String accountId, BigDecimal amount) {
this.accountId = accountId;
this.amount = amount;
}
}
How does the two-pointer switching method work?
Set pa = headA and pb = headB. Loop while pa != pb. When a pointer reaches null, redirect it to the other list's head. Both pointers traverse exactly lenA + lenB nodes, so they align and meet at the intersection.
package com.bank.service;
import com.bank.model.StatementNode;
public class IntersectionFinder {
public static StatementNode findIntersection(StatementNode headA, StatementNode headB) {
StatementNode pa = headA;
StatementNode pb = headB;
while (pa != pb) {
pa = (pa == null) ? headB : pa.next;
pb = (pb == null) ? headA : pb.next;
}
return pa; // either the intersection node or null
}
public static void main(String[] args) {
// Shared tail: joint account statements
StatementNode shared1 = new StatementNode("JOINT", new BigDecimal("50000"));
StatementNode shared2 = new StatementNode("JOINT", new BigDecimal("75000"));
shared1.next = shared2;
// Rajesh's personal chain
StatementNode rajesh1 = new StatementNode("SAV2001", new BigDecimal("10000"));
StatementNode rajesh2 = new StatementNode("SAV2001", new BigDecimal("20000"));
rajesh1.next = rajesh2;
rajesh2.next = shared1; // merges into shared
// Priya's personal chain
StatementNode priya1 = new StatementNode("CUR3001", new BigDecimal("30000"));
priya1.next = shared1; // merges into shared
StatementNode intersection = findIntersection(rajesh1, priya1);
System.out.println("Intersection at: " + intersection.accountId
+ " amount " + intersection.amount);
}
}
Intersection at: JOINT amount 50000
Why does the switching trick work mathematically?
Let list A have length a + c and list B have length b + c, where c is the shared tail. Pointer A travels a + c + b before reaching the intersection. Pointer B travels b + c + a before reaching the intersection. Since a + c + b = b + c + a, they arrive at the same node at the same step.
List A: [R1] -> [R2] -> [JOINT1] -> [JOINT2] -> null
▲
List B: [P1] -> ─────────┘
A travels: a=2 nodes, then c=2 shared, then switches to B: b=1 node = total 5
B travels: b=1 node, then c=2 shared, then switches to A: a=2 nodes = total 5
Both reach JOINT1 at step 3 of their second pass.
How does the length-difference method work?
Compute both list lengths, advance the longer list's pointer by the difference, then walk both in lockstep.
public static StatementNode findIntersectionByLength(
StatementNode headA, StatementNode headB) {
int lenA = length(headA);
int lenB = length(headB);
StatementNode pa = headA;
StatementNode pb = headB;
// Advance the longer list
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) pa = pa.next;
} else {
for (int i = 0; i < lenB - lenA; i++) pb = pb.next;
}
// Walk in lockstep
while (pa != pb) {
pa = pa.next;
pb = pb.next;
}
return pa;
}
private static int length(StatementNode head) {
int len = 0;
while (head != null) { len++; head = head.next; }
return len;
}
Why must the comparison be reference equality?
Two separate nodes can hold the same value without being the same physical node. Intersection is a structural property: the two lists literally share the same node object. In Java, use pa == pb, not pa.amount.equals(pb.amount).
// WRONG: value comparison gives false positive
if (pa.amount.equals(pb.amount)) { ... } // different nodes with same value
// CORRECT: reference comparison detects shared node
if (pa == pb) { ... } // same object in memory
What happens when there is no intersection?
If the lists do not share any nodes, both pointers eventually become null at the same step after one full switch. The loop exits with pa == pb == null, correctly returning null.
package com.bank.service;
import com.bank.model.StatementNode;
import java.math.BigDecimal;
public class NoIntersectionDemo {
public static void main(String[] args) {
StatementNode a = new StatementNode("A1", new BigDecimal("100"));
a.next = new StatementNode("A2", new BigDecimal("200"));
StatementNode b = new StatementNode("B1", new BigDecimal("300"));
StatementNode result = IntersectionFinder.findIntersection(a, b);
System.out.println("Intersection: " + result); // null
}
}
Intersection: null
What are the edge cases?
Both lists empty, one list empty, identical lists (intersection is the head), and lists of very different lengths.
package com.bank.service;
import com.bank.model.StatementNode;
import java.math.BigDecimal;
public class IntersectionEdgeCases {
public static void main(String[] args) {
// Both empty
System.out.println("Both empty: " + IntersectionFinder.findIntersection(null, null));
// Same list (intersection at head)
StatementNode shared = new StatementNode("S1", new BigDecimal("500"));
System.out.println("Same list: " + IntersectionFinder.findIntersection(shared, shared).accountId);
}
}
Both empty: null
Same list: S1
What should a senior engineer know?
The two-pointer switching method is preferred because it needs no explicit length computation and handles all cases uniformly. The reason it terminates even without an intersection is that after one switch each pointer has walked exactly lenA + lenB steps, at which point both are null simultaneously.
In production at National Bank of India, compliance needs to find where Rajesh's personal statement chain and Priya's personal statement chain merge into their joint account chain. The intersection finder identifies the exact junction node so compliance can audit the shared portion.
// Production usage: find where two customer chains join
StatementNode junction = IntersectionFinder.findIntersection(
rajeshStatements, priyaStatements
);
if (junction != null) {
auditService.flagJointAccountUsage(junction);
}
Visual Overview
Y-Shaped Intersection
List A: [R1] ──> [R2] ──┐
├──> [JOINT1] ──> [JOINT2] ──> null
List B: [P1] ───────────┘
Two-Pointer Switching:
pA: R1 → R2 → J1 → J2 → null → P1 → J1 (stop)
pB: P1 → J1 → J2 → null → R1 → R2 → J1 (stop)
Both arrive at J1 at the same step.
No Intersection: List A: [A1] ──> [A2] ──> null List B: [B1] ──> null pA: A1 → A2 → null → B1 → null (stop) pB: B1 → null → A1 → A2 → null (stop) Both become null at the same step → return null.
Key Takeaway
Finding the intersection of two singly linked lists means locating the exact node where two chains merge into one shared tail. The two-pointer switching method is elegant: pointer A walks list A then continues onto list B, while pointer B walks list B then continues onto list A. Both traverse exactly the combined length of both lists, so they are perfectly aligned and meet at the junction node.
If the lists do not intersect, both pointers become null at the same step after one full switch, so the loop exits cleanly and returns null. This termination guarantee is a classic follow-up question, and being able to explain why it works shows understanding rather than memorization.
The comparison must always be reference equality (==), not value equality, because two unrelated nodes can coincidentally carry the same amount. Intersection is a structural property: the lists literally share the same node object in memory.
In our banking system at National Bank of India, Rajesh and Priya each have personal statement chains that merge into a shared joint-account chain, forming a Y-shape. Compliance uses the intersection finder to locate the exact junction node so it can audit the shared portion for regulatory reporting.
Remember one sentence: walk A-then-B and B-then-A; both cover the same total distance and meet at the Y-junction, or both become null if there is none.
---