Write a program to find the node at which the intersection of two singly linked lists begins.

It is a classic and interesting challenge in interviewing. It’s easy to understand and open enough to have multiple solutions, which is useful to distinguish the skill level of candidates.

This algorithm is also useful for beginners to learn, not only it’s fun but also a good demonstration for the trade-off between time and space in algorithm design.

Challenge Description

Here is a sample input:

In this case, 8 is the intersection of two linked lists.

Approach #1: The naive solution

Suppose Linked List A with the length of M, and Linked List B with the length of N, the naive solution should be easy to figure out. By iterating over the elements of linked list A, and check whether the same pointer exists in linked list B.

The overall time complexity is $O(M*N)$.

Approach #2: solution with a set

The time-consuming part of the previous approach is iterating over linked list B multiple times. Can we do better on the time performance?

Yes! But we need some extra memory space.

We need to use a set to store all the pointers of linked list A, then iterate over linked list B in one pass to query whether the current pointer exists in set.

Time complexity: $O(M+N)$, and space complexity: $O(M)$.

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
       set<ListNode*> s;
       ListNode* p = headA;
       while(p) {
           s.insert(p);
           p = p->next;
       }
       p = headB;
       while(p)  {
           if(s.find(p) != s.end()) return p;
           p = p->next;
       }
       return NULL;
    }
};

Approach #3: two pointers

This is a tricky and elegant solution!

We use two pointers to iterate over linked list, PA and PB. If pointer PA reach the tail of linked list A, we redirect it to head of linked list B.

And similar, when PB reach the tail of linked list B, redirect to head of linked list A. Whenever the two pointers are the same, we get the intersection pointer.

Let’s demonstrate how this algorithm works. Suppose the scenario of the two linked lists having intersection pointer:

If we redirect tail’s next to the head of the other linked list, it looks like this:

If two linked lists have intersection pointer, the two pointers will both move forward to length(A)+length(B) positions!

This algorithm also works correctly when there is no intersection between two linked lists, two pointers will both point to NULL when the iteration terminates.

Time complexity: $O(M+N)$, space complexity: $O(1)$.

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pa = headA, *pb = headB;
        while(pa != pb) { 
            pa = pa == NULL? headB : pa->next;
            pb = pb == NULL? headA : pb->next;
        }
        return pa;
    }
};

Preparing for an interview? Check out this!