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.
Here is a sample input:
In this case,
8 is the intersection of two linked lists.
Approach #1: The naive solution
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
Time complexity: $O(M+N)$, and space complexity: $O(M)$.
Approach #3: two pointers
This is a tricky and elegant solution!
We use two pointers to iterate over linked list,
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
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)$.
Preparing for an interview? Check out this!