The intersection of two Sorted Linked Lists

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement:

In this problem, we are given two sorted linked lists and are asked to print a single linked list that contains the common intersection from the two lists.

Let me make this more clear with an example test case:
Linked list 1:

Linked list 2:

The resultant Linked List after the intersection of the above lists 1 and 2 will be:

Problem Statement Understanding:

Let's first understand the problem statement with the help of an example:

If Linked list 1 = 0β†’3β†’4β†’8 and Linked list 2 = 4β†’8β†’9.
Now to find the intersection of the two linked lists, we will have to find the elements which are common in both the linked list 1 and 2 i.e. element which appear in both the lists.

  • As we can see that 4 and 8 appear in both the list 1 and list 2, so they will be included in the final intersection list.
  • 0, 3, 9 appears in only one of the two lists, so we will not include them in the final intersection list.

So, our final intersection list will be 4 β†’ 8.

If Linked list 1 = 6β†’2β†’3β†’9 and Linked list 2 = 2β†’3β†’9.

  • As we can see that 2, 3 and 9 appear in both the list 1 and list 2, so they will be included in the final intersection list.
  • 6 appears in only one of the two lists, so we will not include them in the final intersection list.

So, our final intersection list will be 2 β†’ 3 β†’ 9.

Now, I think from the above examples, it is clear what we are trying to find in this problem. So next we will try to think how we can approach this problem.

Before jumping to the next section of the blog, try to think how you can approach this problem?

Approach 1

Suppose our initial linked lists are β€˜a’ and β€˜b’, the basic idea is to take two pointers, each pointing to the head of one of the two linked list 'a' and 'b'. Now start traversing the linked lists until one of them is completely traversed and while traversing check:

  • If both the elements of the lists are equal, then we need to remove both the nodes from the lists and insert the element to the tail of the dummy LinkedList.
  • Otherwise, we remove the smaller element among both the linked lists.

The dummy linked list which we are referring to above, it's main idea is to take the help of a dummy node variable that will store our final resultant list (dummy LinkedList). The pointer tail will point to the last node in the resultant list, so that the new nodes can be added easily to the resultant list. This dummy node is used as a temporary node.

When we have traversed either of the two given lists completely, then the result is in the dummy list. The values are allocated from the next node of the dummy, i.e. our resultant intersection list starts from the next of the dummy node (dummy.next).

Code Implementation


#include
using namespace std;
struct Node {
    int data;
    Node* next;
};
void push(Node** head_ref, int new_data);
Node* intersectfunc(Node* a, Node* b)
{
    Node dummy;
    Node* tail = &dummy;
    dummy.next = NULL;

    while (a != NULL && b != NULL) {
        if (a->data == b->data) {
            push((&tail->next), a->data);
            tail = tail->next;
            a = a->next;
            b = b->next;
        }
        else if (a->data < b->data)
            a = a->next;
        else
            b = b->next;
    }
    return (dummy.next);
}
void push(Node** head_ref, int new_data)
{
    Node* new_node = (Node*)malloc(
        sizeof(Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
void show(Node* node)
{
    while (node != NULL) {
        cout << node->data <<" ";
        node = node->next;
    }
}
int main()
{
    Node* a = NULL;
    Node* b = NULL;
    Node* intersect = NULL;
    push(&a, 8);
    push(&a, 4);
    push(&a, 3);
    push(&a, 0);
    push(&b, 9);
    push(&b, 8);
    push(&b, 4);
    intersect = intersectfunc(a, b);
    show(intersect);
}

Output

4β†’8

Time Complexity: O(m+n), where m and n are the numbers of nodes in the first and second linked lists, respectively.

Space Complexity: O(min(m, n)), as the output list can store at most min(m, n) nodes.

Can we solve the above problem recursively, try to think?

Approach 2

I can think of another approach using recursion. It will work the same way, but with a recursive function that takes two nodes and returns the intersected node list.

The most efficient idea is to compare the first elements of both the lists:

  • If they are similar, then we call the recursive function with the next node of both the lists and create a node with the common node data and return it.
  • Else, if they are not similar, then we remove the smaller node of both the lists and again call the recursive function.

Algorithm

Start comparing the first elements of the two linked lists:

  • If two elements are similar, then create a new node with the common element and return that node and call the recursive function with the next nodes of the two lists.
  • If they are different, then remove the smaller node and call the recursive function again.

Dry Run

Code Implementation


#include 
using namespace std;
struct Node
{
    int data;
    struct Node* next;
};
struct Node* intersectfunc(struct Node* a,    struct Node* b)
{
    if (a == NULL || b == NULL)
        return NULL;
    if (a->data < b->data)
        return intersectfunc(a->next, b);

    if (a->data > b->data)
        return intersectfunc(a, b->next);
    struct Node* temp = new Node();
    temp->data = a->data;
    temp->next = intersectfunc(a->next,b->next);
    return temp;
}
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
void show(struct Node* node)
{
    while (node != NULL)
    {
        cout << " " << node->data;
        node = node->next;
    }
}
int main()
{
    struct Node* a = NULL;
    struct Node* b = NULL;
    struct Node* intersect = NULL;
    push(&a, 8);
    push(&a, 4);
    push(&a, 3);
    push(&a, 0);

    push(&b, 9);
    push(&b, 8);
    push(&b, 4);
    intersect = intersectfunc(a, b);
    show(intersect);
    return 0;
}

Output

4β†’8

Time Complexity: O(m+n) where m and n are the numbers of nodes in the first linked list and second linked list respectively.

Space Complexity: O(max(m, n)), as the output list can store at most min(m,n) nodes .

This blog tried to discuss the problem when we are given two linked lists and we have to return the intersection list of the two. If you want to practice more questions on linked lists, feel free to solve them at Linked List.

Previous post Delete N nodes after M nodes of a Linked List
Next post Given a Linked List move the last element to the front

Leave a Reply

Your email address will not be published. Required fields are marked *