Intersection of Two Linked Lists

Problem: Intersection of Two Linked Lists

The general idea is to connect the tail of one list to its head thus forms a cycle. We use two pointers going from head of second list, one going two steps head and one going one step ahead. Once these two pointers meet again, their distance to the intersection pointer surely equals to the non-intersection part of second list.

Code in Python:

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB: return None

        tailA = headA
        while tailA.next:
            tailA = tailA.next
        tailA.next = headA

        p1, p2 = headB, headB
        while p1 and p2:
            p1, p2 = p1.next, p2.next
            if p2: p2 = p2.next
            if p1 == p2: break

        ans = None
        if p1 and p2 and p1 == p2:
            p1 = headB
            while p1 != p2:
                p1, p2 = p1.next, p2.next
            ans = p1

        tailA.next = None
        return ans