Intersection of Two Linked Lists
Return the node where two singly linked lists first intersect, or null if they never do.
Intuition
Two walkers, one starting on each list, that hop to the other list's head when they finish. After at most one switch each, they have walked the same total distance — so they meet at the intersection (or both reach null together).
Two pointers that switch lists on reaching the end both travel exactly lenA + lenB steps, so they arrive at the intersection together regardless of the original length difference. If there's no intersection they both hit None at the same moment, which the same loop condition catches for free.
Approach
The set solution costs memory
Put every node of list A into a hash set, then scan list B for the first node already in the set — that node is the intersection. It's O(m + n) time but O(m) space. The clever solution reaches the same node with two pointers and no extra memory, by equalizing the lists' lengths implicitly.
Make both walkers travel the same distance
The only reason a naive single pass fails is that the two lists usually have different lengths before the shared tail, so the pointers reach the junction out of sync. Fix that by having each pointer, on hitting the end of its list, jump to the other list's head. After this switch, both pointers will have walked exactly lenA + lenB nodes — the length difference cancels out, putting them in lockstep by the time they reach the shared portion.
Walk until the pointers coincide
Step a and b forward one node at a time, redirecting each to the opposite head when it falls off the end. They become equal precisely at the first shared node. If the lists never intersect, both pointers reach null on the same step and the loop ends returning null — which doubles as the 'no intersection' answer. O(m + n) time, O(1) space.
Solution & live demo
Common pitfalls
Switching on a.next instead of a
a = a.next if a.next else headB
a = a.next if a else headB
Switching one node early means each pointer walks lenA + lenB - 1 steps, so they never align. The switch must happen after falling off the end, which is why the null value itself is the trigger.
Comparing values rather than identity
while a.val != b.val:
while a is not b:
The question asks where the lists share a node, not where they happen to hold equal numbers. Two distinct nodes with the same value would report a false intersection.
Guarding the loop against None
while a and b and a is not b:
while a is not b:
In the non-intersecting case both pointers become None on the same iteration, so a is not b is false and the loop exits returning None — exactly the required answer. Adding null guards exits early and asymmetrically, returning a non-null node that isn't an intersection.
Edge cases
Both pointers eventually hit null on the same step, and the loop exits returning null.
No switch is even needed; the pointers meet at the intersection on the first traversal.
The pointer-swap math still aligns them at that first shared node.