Intersection of two Sorted Linked lists

Algorithm

Time Complexity: O(m+n) where,

m = number of nodes in list 1
n = number of nodes in list 2

Step 1 : Create a function which takes the two linked lists as arguments and gives out a new linked list with the intersection of elements.

Step 2 : Create a NULL node, where we can append the common elements.

Step 3 : Stores last value entered, as intersection has only one instance of the value common between the 2 lists.

Step 4 : traverse the two lists until one is fully traversed or both are traversed.
a)     Compare the elements such that if element in list 1 is greater than element in list 2, traverse in list 2.
b)    Compare the elements such that if element in list 2 is greater than element in list 1, traverse in list 1.
c)    If both are equal, insert the element at the end of the list. Because, it should be in sorted form.
d)    While adding into the list, compare with last entered value such that element should not be added twice. If added update last entered value, such that next time

Step 5 : on the given two linked lists, call this function. It will give a pointer to head of new linked list where elements are intersection of the given two linked lists.

C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LL{
int data;
LL *next;
};

{

{
}

else{

while(temp->next!=NULL)
temp=temp->next;

temp->next=new LL;
temp=temp->next;
temp->data=dataToBeInserted;
temp->next=NULL;
}
//O(number of nodes)
}

{
int last_entered_value; //stores last value entered as intersection has only one instance of the value common between the 2 lists

while(temp1 and temp2) //till one of the list or both lists are traversed
{

if(temp1->data < temp2->data)
temp1 = temp1->next;

else if(temp2->data < temp1->data)
temp2 = temp2->next;

else
{
if(last_entered_value != temp1->data)
{
insertAtEnd(&finalList,temp1->data);
last_entered_value = temp1->data;
}
temp1 = temp1->next;
temp2 = temp2->next;
}
}

}

{
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

struct LL *head1 = NULL; //initial list has no elements

cout <<"First list is :-\n";

cout <<"\nSecond list is :-\n";