Fast Python solution (372 ms) O(n) time O(1) space


  • 0
    L

    This fast solution aligns the two linked list at their ends, and compares node references starting from the nth node from the last, n being the length of the shorter list. Any comments are greatly appreciated.

    class Solution(object):
            def getIntersectionNode(self, headA, headB):
                if not headA or not headB:
                    return None
                a = self.countLen(headA)
                b = self.countLen(headB)
                if a < b:
                    a,b = b,a
                    headA,headB = headB,headA
                while a > b:
                    headA = headA.next
                    a -= 1
                while headA:
                    if headA == headB:
                        return headA
                    headA = headA.next
                    headB = headB.next
                return None
                
            def countLen(self, head):
                n = 0
                while head:
                    head = head.next
                    n += 1
                return n

  • 0
    J

    It's not really O(N) right? You have O(N) after the two countLen() calls already. It's O(n+m+max(n, m)). The code is clean though, apart for the camelCase :)


Log in to reply
 

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