a, b = headA, headB
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
Python solution (5 lines)


@senior Explanation: Without loss of generation, let's assume list A is
k
elements longer than list B. (k
>=0)
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 whenb
reaches the end of list,a
is stillk
nodes away from the end. Thenb
goes to the head of list A, continue untila
reaches the end of list and goes back to the head of list B.
At this point,b
isk
nodes away from the head of list A. Since list A isk
elements longer than list B, we can conclude that botha
andb
are bothlengthOf(list B)
away from the end of the list (regardless of the existence of the intersection). Tha meansa
andb
are samelength away from the intersection (or null).
From now on, continue the loop, until we find the intersection (or null).
