visual walkthrough
Intersection of Two Linked Lists
Switching heads equalises path lengths, an elegant trick.
The idea
Two lists that share a tail meet at one node and run together after it. The trouble is they may reach it after different numbers of steps.
If each pointer walks its own list and then the other one, both walk the same total distance, so they arrive at the shared node (or at null) at the same moment.
Complexity
| approach | time | space |
|---|---|---|
| Remember A's nodes | O(n + m) | O(n) |
| Switch heads | O(n + m) | O(1) |