O(m + n) O(1)
Intuition
Two pointers that switch to the other list's head after reaching the end travel the same total distance, so they align at the intersection.
Explanation
Equalize the path lengths
List A has length m, list B has length n. Walk pointer a along A then B, and pointer b along B then A. After at most m + n steps both have travelled m + n nodes, so they arrive at the shared suffix together:
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a
If the lists intersect, a and b meet at the first shared node. If they don't, both become None at the same step and the loop returns None.
Worked example
A = 4 -> 1 -> 8 -> 4 -> 5, B = 5 -> 6 -> 1 -> 8 -> 4 -> 5 sharing the suffix starting at 8. The pointers realign and meet at the node with value 8.
Complexity
- Time: O(m + n).
- Space: O(1).
Implementation
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a;
}
}