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).
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
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.