Intersection of Two Lists
Walk pa down A then B and pb down B then A; they meet at the shared node after the same distance, or at null together.
Decision · step 5 of 9List Pointer Puzzles: Two lists sharing a tail
pa moves to 6. pb ran off the end of B, so it restarts at A's head, 1.
What you will see
Two pointers start on different lists; after switching lists once they meet at the intersection.
Cost
| Best | O(n + m) |
|---|---|
| Average | O(n + m) |
| Worst | O(n + m) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Each node announces its value and what it points to; each step announces the pointer change ("node 3 now points to node 5").
Reduced motion: Pointer arrows redraw in place with a brief emphasis instead of animating the detach and reattach.
Before this
Taught by the same lesson
List Pointer Puzzles covers these too, in the same run.