Leetcode 160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/

The simple thought is to get lengths of two lists, and make them start with the same distance from tails. This method will use 3 iterations.

There is an improved method. Even two lists' lengths differ, their sum is the same one. So if we make two pointers starting with heads, and switch to another head when finishing this lists, actually the effect is same with simple thought. While this method saves time.

Solution:

# T:O(m+n) S:O(1)
class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        curA, curB = headA, headB
        tailA, tailB = None, None
        
        while curA and curB:
            if curA == curB:
                return curA
                
            if curA.next:
                curA = curA.next
            elif tailA is None:
                tailA = curA
                curA = headB
            else:
                break
            
            if curB.next:
                curB = curB.next
            elif tailB is None:
                tailB = curB
                curB = headA
            else:
                break

Run Time: 436 ms