If length of two lists are equal, you can iterate a node on each list one by one, and when intersection appears we can detect by checking the
val of node is the same.
So, what if the length of two lists are different? The answer is easy,
- First , measure length of both lists
- Iterate a node on a longer list, until the remaining length becomes equal to the shorter one
It's guaranteed that there is no intersection during iteration of longer list on step2, because if such intersection exists, a shorter list would have longer length than the longer list.
Then, after step2, the problem is come down to the same problem when two lists' length are equal 🤓
def getIntersectionNode(self, headA, headB): """ :type head1, head1: ListNode :rtype: ListNode """ if not headA or not headB: return None # measure length of listA and listB lenA, lenB = 0, 0 curA, curB = headA, headB while curA or curB: if curA: curA, lenA = curA.next, lenA + 1 if curB: curB, lenB = curB.next, lenB + 1 # ensure A is always longer if lenB > lenA: headA, headB, lenA, lenB = headB, headA, lenB, lenA curA, curB, diff = headA, headB, lenA - lenB # iterate the longer listA until diff becomes 0 while diff > 0: curA, diff = curA.next, diff-1 # iterate through both lists until intersection found while curA and curB: if curA.val == curB.val: return curA curA, curB = curA.next, curB.next return None