Performing Intersection of two Sorted Linked Lists in C++

This article discusses a method for performing the intersection of two sorted linked lists in C++. ‘Intersection‘ refers to finding the elements common to both the sets. In this case, we find the values that are common to both the linked lists.

For example. Let,

1 -> 2 -> 5 -> 7 -> 9 -> 12 -> 56 -> 90 -> 123

1 -> 2 -> 3 -> 6 -> 8 -> 9 -> 15 -> 46 -> 99 -> 223

 

be two linked lists. Then, their intersection should print the following:

 

1 -> 2 -> 9

 

The approach to solving this problem is to increment pointers to the nodes of either list in a particular manner. We first input the elements from the user and form a linked list. The same is repeated to form the other linked list.

Once we have both the linked lists, we increment the pointers to individual nodes in the following manner. Since we operate only on sorted linked lists, this allows us to exploit the property that if any node in the first list has a lesser value than the considered node. Then it is guaranteed that there are no common nodes before this, had the same value as that of any node in the second list.

An extension of the same allows us to cut short on the number of checks made. If a node in any list points to NULL, that is, reaches the end of the list. Then it is guaranteed that there are no more common elements to both the linked lists.

With the above points kept in mind, we implement our logic. Now, have a look at the code.

The code

Below is our C++ code where we can see the performance of the intersection of two sorted linked lists:

#include<iostream>

using namespace std;

struct node
{
    int number;
    node *next;
};

node *start1 = NULL, *temp = NULL, *start2 = NULL;

node *create(int num)
{
    node *newnode = new node;

    newnode -> number = num;
    newnode -> next = NULL;

    return newnode;
}

void insertNode(int value)
{
    temp -> next = create(value);
    temp = temp -> next;
}

void display(node *start)
{
    node *tempPtr = start;

    while(tempPtr != NULL)
    {
        cout<<tempPtr -> number<<" -> ";
        tempPtr = tempPtr -> next;
    }

    cout<<"NULL "<<endl<<endl;

}

int main()
{
    int num;
    char ch;


    start1 = temp = create(0);

    do
    {
        cout<<"ENTER NUMBER : ";
        cin>>num;

        insertNode(num);

        cout<<"DO YOU WANT TO CONTINUE ?";
        cin>>ch;

    }while(ch == 'y' || ch == 'Y');

    start1 = start1->next;

    display(start1);

    temp = NULL;
    start2 = temp = create(0);

    do
    {
        cout<<"ENTER NUMBER : ";
        cin>>num;

        insertNode(num);

        cout<<"DO YOU WANT TO CONTINUE ?";
        cin>>ch;

    }while(ch == 'y' || ch == 'Y');

    start2 = start2->next;

    display(start2);

    node *temp1 = start1;
    node *temp2 = start2;

    
    cout<<"INTERSECTION : :<<endl<<endl;

    while(temp1 != NULL && temp2 != NULL)
    {
        if(temp1 -> number == temp2 -> number)
        {
            cout<<temp2 -> number<<" -> ";
            temp1 = temp1 -> next;
            temp2 = temp2 -> next;
        }

        else if(temp1 -> number < temp2 -> number)
        {
            temp1 = temp1 -> next;
        }

        else
        {
            temp2 = temp2 -> next;
        }

    }

    return 0;
}

 

Below is the given output of the above code:

ENTER NUMBER : 1
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 2
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 5
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 8
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 12
DO YOU WANT TO CONTINUE ?n
1 -> 2 -> 5 -> 8 -> 12 -> NULL

ENTER NUMBER : 2
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 3
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 5
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 8
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 9
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 23
DO YOU WANT TO CONTINUE ?y
ENTER NUMBER : 45
DO YOU WANT TO CONTINUE ?n
2 -> 3 -> 5 -> 8 -> 9 -> 23 -> 45 -> NULL

INTERSECTION:

2 -> 5 -> 8 ->

Analysis

As mentioned above, we first form both the linked lists. We initially add ‘0’ to the beginning of the list, this, however, is not a compulsion. It has been done for easier implementation, hence better explainability and comprehension. This does not make any change to the implementation as before we even compare we neglect this explicitly added ‘0’.

Now, we check if the pointers pointing to the start node of both the linked lists have the same value. If yes, we print the value and increment both the pointers. If the pointer pointing to the node of the first list has a value lesser than that of the second list, we increment the pointer of the first list. This is done since we know that there are no common elements before that since the list is sorted.

If the node of the second list has a value lower than that of the first list, we increment the pointer of the second list. We increment the pointer of that list which has a lower value when compared with the corresponding nodes pointed to. This is continued till any one of the nodes points to NULL, that is, reaches the end of the list.

Feel free to read the following articles:

 

Leave a Reply

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