O(m+n) time, O(1) space but need to temporarily modify the structure.
a1 ->->-> c1 ->->-> c3 ↑ | b1 ->->
- Find the length of (a1->c3), countA, and get the tail
- Find the length of (b1->c3), countB, get the tail c3, and reverse
the whole (b1->c3) link to (c3->b1)
- Find the length of (a1->b1), countX
- Reverse (c3->b1) back to (b1->c3)
- If the first two tails are not equal, return None
- Proceed from a1 by (countA - (countA+countB-countX+1)/2) nodes, and
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) self.reverseNodes(tailB) if tailA is not tailB: return None for _ in range(countA - (countA+countB-countX+1)/2): headA = headA.next return headA