My concise python solution, run in O(n) time and O(1) memory


  • 5
    class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        if not headA or not headB:return None
        a,b=headA,headB
        ans = None
        while a or b:  
            if not a:   a=headB
            if not b:   b=headA
            if a==b and not ans: ans=a
            a , b = a.next,b.next
        return ans

  • 0
    T

    The variable ans is optional right?

    class Solution:
        # @param two ListNodes
        # @return the intersected ListNode
        def getIntersectionNode(self, headA, headB):
            if not headA or not headB:return None
            a,b=headA,headB
            ans = None
            while a or b:  
                if not a:   a=headB
                if not b:   b=headA
                if a is b: return a# and not ans: ans=a
                a , b = a.next,b.next
            #return ans

  • 0
    V

    brilliant answer!


  • 0
    C

    much better than my solution that forms a loop first and then finds the loop starting point, which although runs in O(n) O(1), but modifies the pointers, and is ugly.


Log in to reply
 

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