Real O(n) time not O(n + m), O(1) space, use reverse list and is easy to understand


  • 0
    W

    it is O(n) time but slower than the two pointer, hope somebody get some helpful tips to improve it

     def getIntersectionNode(self, headA, headB):
            """
            :type head1, head1: ListNode
            :rtype: ListNode
            """
            # there exists
            # lista = k + b = la, listb = c + b = lb
            # reverse lista, and count lc from the listb  listc = k + c = lc
            # easy to get k = (la - lb + lc - 1) / 2, and the kth node in lista is the intersection node
            def reverse_list(head):
              if not head: return
              chead, ohead = head.next, head
              ohead.next = None
              while chead:
                temp_head = chead.next
                chead.next = ohead
                ohead = chead
                chead = temp_head
              return ohead
    
            if not (headA and headB): return
            if headA == headB: return headA
    
            la, lb, lc = 0, 0, 0
            ha, hb = headA, headB
            while ha.next:
              ha, la = ha.next, la + 1
            while hb.next:
              hb, lb = hb.next, lb + 1
    
            if ha != hb:
              # if the last node don't equal to other one
              return None
            else:
              la, lb = la + 1, lb + 1
    
            revr_list = reverse_list(headA)
            hb = headB
            while hb:
              hb, lc = hb.next, lc + 1
            # need make the lista back to origin
            reverse_list(revr_list)
            ka = (la - lb + lc - 1) / 2
            while ka > 0:
              headA, ka = headA.next, ka - 1
            return headA
    

Log in to reply
 

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