A new method different from any of the solution provided

  • 1

    O(m+n) time, O(1) space but need to temporarily modify the structure.

    a1 ->->-> c1 ->->-> c3
       b1 ->->

    Method description:

    1. Find the length of (a1->c3), countA, and get the tail
    2. Find the length of (b1->c3), countB, get the tail c3, and reverse
      the whole (b1->c3) link to (c3->b1)
    3. Find the length of (a1->b1), countX
    4. Reverse (c3->b1) back to (b1->c3)
    5. If the first two tails are not equal, return None
    6. Proceed from a1 by (countA - (countA+countB-countX+1)/2) nodes, and
      return that

    It tries to count the length of the branches.

    436ms in Python which is among the top 3%

    class Solution:
        # Count the nodes and return the tail and the length
        # return (tail, len)
        def countNodes(self, head):
            count = 1
            while head.next is not None:
                count += 1
                head = head.next
            return (head, count)
        # Count the nodes, reverse the whole link, and return the original tail and the length
        # return (tail, len)
        def reverseNodes(self, head):
            count = 1
            prev = head
            now = prev.next
            prev.next = None
            while now is not None:
                count += 1
                temp = now.next
                now.next = prev
                prev = now
                now = temp
            return (prev, count)
        # @param two ListNodes
        # @return the intersected ListNode
        def getIntersectionNode(self, headA, headB):
            if headA is None or headB is None:
                return None
            tailA, countA = self.countNodes(headA)
            tailB, countB = self.reverseNodes(headB)
            _, countX = self.countNodes(headA)
            if tailA is not tailB:
                return None
            for _ in range(countA - (countA+countB-countX+1)/2):
                headA = headA.next
            return headA

Log in to reply

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