Share my Python code


  • 0
    Y

    Hi, here is my Python code costing about 900ms.
    I saw someone got less than 500ms with Python, how's that done? Any one share a fast Python code?

    class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        if not headA or not headB:
            return None
    
        # Find the tail of list A
        tailA = headA
        while tailA.next:
            tailA = tailA.next
        tailA.next = headB  # Link A's tail to B's head
    
        # Find loop position
        slow = fast = headA
        while True:
            if not fast.next or not fast.next.next:
                # Restore tail of list A and return
                tailA.next = None
                return None
            else:
                slow = slow.next # Safe to push slow
                fast = fast.next.next
                if slow == fast:
                    fast = headA
                    break
        
        while fast != slow:
            fast = fast.next
            slow = slow.next
    
        # Fast and slow both point to loop entrance
        # Restore tail of list A and return
        tailA.next = None
        return fast

  • 1
    B

    This is my solution, much shorter, runs around 700 ms.

    class Solution:
        # @param two ListNodes
        # @return the intersected ListNode
        def getIntersectionNode(self, headA, headB):
            pA, pB = headA, headB
            
            while pA != pB:
                try:
                    pA = pA.next
                except:
                    pA = headB
                    
                try:
                    pB = pB.next
                except:
                    pB = headA
            return pA
    

    This one is even shorter. But runs a little bit slower. This also explains in Python asking for forgiven is better than asking for permission. For solution takes less than 500 ms, I have no ideas :-(

    def getIntersectionNode(self, headA, headB):
        pA, pB = headA, headB
        
        while pA != pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA
        return pA

  • 0
    B

    I realized that there is a bug in my solutions. That will fall into endless loop if be given 2 none-empty lists without intersection. I am sorry about that and also surprised that the solution could be accepted! Basically we need a bool guard to guarantee the pointer switch only occur once. After that just simply return None if a pointer runs into None again.


  • 0
    Z

    Question: Why 'if pA else headB'?? Do you need to start from the headA if pA run out? Thanks!!


  • 0
    Z

    Could you please explain more about line: p1 = p1.next if p1 else headB? Thanks so much!!


  • 0
    B

    This is the python equivalent for C/C++ operator ?:
    p1.next if p1 else headB just like:
    p1==None?headB:p1.next


Log in to reply
 

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