Intersection of Two Linked Lists

Problem Id: 160 Difficulty: Easy


Intuition

Solution


class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        index1 = headA
        len1 = 1
        while index1.next:
            len1 += 1
            index1 = index1.next
        index2 = headB
        len2 = 1
        while index2.next:
            len2 += 1
            index2 = index2.next
        if index1 != index2:
            return None

        while len1 > len2:
            headA = headA.next
            len1 -= 1
        while len2 > len1:
            headB = headB.next
            len2 -= 1

        while headA != headB:
            headA = headA.next
            headB = headB.next
        return headA