Intersection Of Two Linked Lists

Coder’s Cat
Feb 24, 2020 · 3 min read
Image for post
Image for post
Mike Enerio @ unsplash.com

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:

Image for post
Image for post
credit leetcode.com

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

Approach #1: The naive solution

Suppose Linkedlist A with the length of M, and Linkedlist 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 𝑂(𝑀∗𝑁).

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 current pointer exists in set.

Time complexity: 𝑂(𝑀+𝑁), and space complexity: 𝑂(𝑀).

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 the linked lists, 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 has intersection pointer:

Image for post
Image for post

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

Image for post
Image for post

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

Image for post
Image for post

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

Time complexity: 𝑂(𝑀+𝑁), space complexity: 𝑂(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;
}
};

The Startup

Medium's largest active publication, followed by +771K people. Follow to join our community.

Thanks to Zack Shapiro and Yenson Lau

Coder’s Cat

Written by

http://coderscat.com Write stuff about programming languages, algorithms, and architecture.

The Startup

Medium's largest active publication, followed by +771K people. Follow to join our community.

Coder’s Cat

Written by

http://coderscat.com Write stuff about programming languages, algorithms, and architecture.

The Startup

Medium's largest active publication, followed by +771K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface.

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox.

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store