Pattern visualizer
Intersection of Two Linked Lists
Two lists that merge share every node from the join onward, but their parts BEFORE the join can differ in length, so two pointers stepping together from the two heads are out of phase and never coincide. The trick is to let each pointer, on reaching the end of its list, continue from the head of the other list. Then both pointers travel exactly the same total distance (A's part + B's part + the shared tail) before arriving at the join, so on that second lap they hit the first shared node on the same step. If the lists never meet, both pointers reach NULL together after the same distance, and the loop ends returning NULL. The row below shows A's own nodes, then B's own nodes, then the shared tail once. Animated on: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]. The two lists share the same tail nodes 8 -> 4 -> 5 (same objects, not just equal values). Return the node where they first join. Answer: the node with value 8..
Two pointers that swap lists at the end walk equal distances
List A has 2 nodes of its own, list B has 3, and both then run into the same 3-node tail (tinted). pA starts at A's head and pB at B's head. A and B have different lengths, so walking them in lockstep would never line the two pointers up on the shared node — unless each pointer also walks the OTHER list, which makes both trips exactly 2 + 3 + 3 nodes long.
1FUNCTION intersection(headA, headB)2 pA <- headA3 pB <- headB4 WHILE pA != pB5 IF pA = NULL6 pA <- headB7 ELSE8 pA <- NEXT(pA)9 IF pB = NULL10 pB <- headA11 ELSE12 pB <- NEXT(pB)13 RETURN pA
← / → step · space play · Home restart