a, b = headA, headB while a != b: a = a.next if a else headB b = b.next if b else headA return a
@senior Explanation: Without loss of generation, let's assume list A is
k elements longer than list B. (
If list A is as long as list B, then obviously the returned node will be the intersection if there is an intersection, or null if there is no intersection.
If list A is longer than list b, then when
b reaches the end of list,
a is still
k nodes away from the end. Then
b goes to the head of list A, continue until
a reaches the end of list and goes back to the head of list B.
At this point,
k nodes away from the head of list A. Since list A is
k elements longer than list B, we can conclude that both
b are both
lengthOf(list B) away from the end of the list (regardless of the existence of the intersection). Tha means
b are same-length away from the intersection (or null).
From now on, continue the loop, until we find the intersection (or null).
@skw_kevin Your explanation is so clear and great, thank you!
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.