Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed.

For example, let the first linked list be 1->2->3->4->6 and second linked list be 2->4->6->8, then your function should create and return a third list as 2->4->6.

In the program first I sorted the link list and then wrote a function to return a list with intersection.

#include
#include

using namespace std;

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

Node *intersection( Node* listOne, Node* listTwo);

int main()
{
Node *list1 = new Node();
Node *list2 = new Node();
Node *intersectionList  = new Node();

list1 -> data = 5;
list1 -> next = NULL;

list2 -> data = 3;
list2 -> next = NULL;

cout << "List 1 before Sorting: " << endl;
display (list1);

cout << "List 2 before Sorting: " << endl;
display (list2);

sortList(&list1);
cout << "List 1 After Sorting: " << endl;
display (list1);

sortList(&list2);
cout << "List 2 After Sorting: " << endl;
display (list2);

intersectionList = intersection(  list1, list2);
cout << "Intersection List: " << endl;
display (intersectionList);

delete list1;
delete list2;

getch();
}

{

}
{

while(cur)
{
if(cur -> next == NULL)
{
return;
}
cur = cur -> next;

}

}

{

while(cur)
{
if ( cur -> next == NULL)
{
cout << cur -> data;
}
else
cout << cur -> data << ",";
cur = cur -> next;
}

cout << endl;
cout << endl;
}
/*

{
Node * me = parent -> next;
parent -> next = NULL;
Node *child = me -> next;

while(child)
{
me -> next = parent;
parent = me;
me = child;
child = child -> next;
}
me -> next = parent;
}*/

{
Node *temp = new Node();

int flag = 0;
temp = cur -> next;

do{
flag = 0;
while(cur -> next != NULL)
{
if (cur -> data > temp ->data )
{
temp -> data = cur -> data + temp -> data;
cur -> data = temp -> data - cur -> data;
temp -> data = temp -> data - cur -> data;
cur = cur -> next;

if (cur -> next != NULL)
{
temp = cur -> next;

}
flag = 1;
}
else //if(cur -> next != NULL)
{

if (cur -> next != NULL)
cur = cur -> next;
if (cur -> next != NULL)
temp = cur -> next;
}
}

if(temp == cur)
{
temp = cur -> next;
}

} while (flag == 1);

}

Node *intersection( Node* listOne, Node* listTwo)
{
Node *cur1 = listOne;
Node *cur2 = listTwo;
Node *temp = new Node();
int pos = 0;

while(cur1 || cur2)
{
if( cur1 -> data > cur2 ->data )
if(cur2 -> next == NULL)
return temp;
else
cur2 = cur2 -> next;

if( cur1 -> data < cur2 ->data )
if(cur1 -> next == NULL)
return temp;
else
cur1 = cur1 -> next;

if( cur1 -> data == cur2 ->data )
{
if(pos == 0)
{
temp -> data = cur2 -> data;
pos++;
}
else