Python O(n) time, O(1) solution with explanation


  • 0

    If length of two lists are equal, you can iterate a node on each list one by one, and when intersection appears we can detect by checking the val of node is the same.

    So, what if the length of two lists are different? The answer is easy,

    1. First , measure length of both lists
    2. Iterate a node on a longer list, until the remaining length becomes equal to the shorter one

    It's guaranteed that there is no intersection during iteration of longer list on step2, because if such intersection exists, a shorter list would have longer length than the longer list.
    Then, after step2, the problem is come down to the same problem when two lists' length are equal 🤓

        def getIntersectionNode(self, headA, headB):
            """
            :type head1, head1: ListNode
            :rtype: ListNode
            """
            if not headA or not headB:
                return None
            
            # measure length of listA and listB
            lenA, lenB = 0, 0
            curA, curB = headA, headB
            while curA or curB:
                if curA:
                    curA, lenA = curA.next, lenA + 1
                if curB:
                    curB, lenB = curB.next, lenB + 1
            
            # ensure A is always longer
            if lenB > lenA:
                headA, headB, lenA, lenB = headB, headA, lenB, lenA
            
            curA, curB, diff = headA, headB, lenA - lenB
            # iterate the longer listA until diff becomes 0
            while diff > 0:
                curA, diff = curA.next, diff-1
            # iterate through both lists until intersection found
            while curA and curB:
                if curA.val == curB.val:
                    return curA
                curA, curB = curA.next, curB.next
            return None
    

Log in to reply
 

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