Python solution (5 lines)


  • 4
    D
    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a
    

  • 0
    S

    @Dan
    can't understand
    ...(。•ˇ‸ˇ•。) ...


  • 0
    S

    so clever...why cannot I think of it....


  • 1
    S

    @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 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, b is k nodes away from the head of list A. Since list A is k elements longer than list B, we can conclude that both a and b are both lengthOf(list B) away from the end of the list (regardless of the existence of the intersection). Tha means a and b are same-length away from the intersection (or null).
    From now on, continue the loop, until we find the intersection (or null).


  • 0
    S

    @skw_kevin Your explanation is so clear and great, thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.