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;
};

void addFirst (Node **head, int data);
void display (Node *head);
void addLast (Node *head, int data);
void display (Node *head);
Node *reverse (Node **head);
Node *sortList ( Node **head);
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;

	addLast(list1, 4);
	addLast(list1, 9);
	addLast(list1, 3);
	addLast(list1, 6);
	addLast(list1, 1);
	addLast(list1, 12);

	
	addLast(list2, 4);
	addLast(list2, 5);
	addLast(list2, 9);
	addLast(list2, 7);
	addLast(list2, 2);
	addLast(list2, 1);
	addLast(list2, 12);
	addLast(list2, 10);

	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();
}

void addFirst (Node **head, int data)
{
	
	Node *newHead = new Node();
	
	newHead -> data = data;
	newHead -> next = *head;
	*head = newHead;
	

}
void addLast (Node *head, int data)
{
	Node *cur = head;
	Node *newHead = new Node();
	newHead -> data = data;

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

	}
	
}

void display (Node *head)
{
	Node *cur = head;

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

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

Node *reverse (Node **head)
{
	Node *parent = *head;
	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;
	*head = me;
	return *head;
}*/

Node *sortList (Node **head)
{	
	Node *cur = *head;
	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)
	{
		cur = *head;
		temp = cur -> next;
	}


	
	} while (flag == 1);
	
	//cur = *head;

	return *head;

}

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
				addFirst(&temp, cur2 -> data); 
			cur2 = cur2 -> next; 
			cur1 = cur1 -> next; 

		}
	}
	return temp;
}