Intersection of Two Linked Lists

160. Intersection of Two Linked Lists

Solution 1

1. The intersection must be the “tail” of both linked list.

2. Use two pointer to traverse the linked list from different head, we can achieve the route as A + intersection + B + intersection and B + intersection + A + intersection.

3. After A/B + intersection + B/A, the pointers are pointing to the same position. Return the pointer’s position.

4. If the pointers never meet, there is no intersection between them.

def getIntersectionNode(self, headA, headB):
    """
    :type head1, head1: ListNode
    :rtype: ListNode
    """
    pA, pB = headA, headB
    
    while pA != pB:
        if pA is None:
            pA = headB
        else:
            pA = pA.next
        if pB is None:
            pB = headA
        else:
            pB = pB.next
    return pA