AlgoScope

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.

Linked list algorithms, algorithm, intermediate
pa moves to 6. pb ran off the end of B, so it restarts at A's head, 1. 123956paheadBpb
pa moves to 6. pb ran off the end of B, so it restarts at A's head, 1. 123956paheadBpb

List Pointer Puzzles: Two lists sharing a tail

Decision, step 5 of 9

pa moves to 6. pb ran off the end of B, so it restarts at A's head, 1.

How list pointer puzzles works

Cost

Best
O(n + m)
Average
O(n + m)
Worst
O(n + m)
Space
O(1)

Taught by the same lesson

List Pointer Puzzles covers these too, in the same run.