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
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
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.
Question: Why 'if pA else headB'?? Do you need to start from the headA if pA run out? Thanks!!
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.