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.
List 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.
Cost
- Best
- O(n + m)
- Average
- O(n + m)
- Worst
- O(n + m)
- Space
- O(1)
Before this
Taught by the same lesson
List Pointer Puzzles covers these too, in the same run.