How do you find the node where two linked lists intersect?
Walk two pointers, one from each head. When a pointer reaches the end, redirect it to the head of the other list. After at most two passes they meet at the intersection node, or both become null if there is none.
Explain it simply
Two roads, A and B, merge into one highway. Road A is 5 km before the merge and road B is 3 km, then the highway is common. If two cars start at the same time, one on each road, the car on B arrives at the end sooner.
Fix the length difference by making each car, on reaching the end of its own road, jump to the start of the other road. Both then travel exactly (A + B + common) kilometres and arrive at the merge point together.
Example
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function getIntersection(a, b) {
let p = a;
let q = b;
while (p !== q) {
p = p ? p.next : b;
q = q ? q.next : a;
}
return p;
}
const common = new ListNode(8, new ListNode(9));
const a = new ListNode(1, new ListNode(2, common));
const b = new ListNode(5, common);
console.log(getIntersection(a, b).val); // Output: 8
console.log(getIntersection(a, new ListNode(7))); // Output: nullComplexity
Time O(n + m), space O(1).
What to say in the interview
"Each pointer walks its own list and then switches to the other list. Both cover the same total length, so they meet at the intersection or both reach null together. Time is O(n + m) and space is O(1); a hash set of visited nodes also works but costs O(n) memory. I compare node references, not values."
Common mistakes
- Comparing node values instead of node references.
- Not switching the pointer on null, so the loop never ends when lists do not intersect.