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

The idea of solution is the following:

  1. Calculate lengths of both lists and evaluate difference.
  2. Make this number of steps for the longest list, pointer p1 and pointer p2 put to start of short list.
  3. Move pointers p1 and p2 one by one until we have the same value: it will be either common element or it will be None element.

Suprasingly all this can be done in one loop: let us look at the line currB = headA if currB is None else currB.next. What we are doing here is when some list finishes we start to traverse another list. Imagine the case:

First list has a elements before intersection and b elements after intersection. Second list has c elements before intersection and b elements after intersection, and c > a.

  1. On the first step we will reach end of first list and for the second list we will be c-a elements before end.
  2. On the second step our short list ended, so now we start to traverse long list and after c-a steps one of the pointers will be in the beginning of short list and another will be c-a steps from the long list.
  3. Finally, we move both pointers with speed one and either we will have common element or they both reach the end in the same time and in this case they will have common None element.

Complexity: we traverse both lists twice, so we will make no more than 2n + 2m = O(m+n). Space complexity is O(1).

class Solution:
    def getIntersectionNode(self, headA, headB):
        currA, currB = headA, headB
        
        while currA != currB:
            currB = headA if currB is None else currB.next
            currA = headB if currA is None else currA.next
            
        return currA

If you like the solution, you can upvote it on leetcode discussion section: Problem 0160