Complete two

Complete the listIntersection function that accepts two node * (the heads of two linked lists) and returns a node * that points to the head of a new linked list. This function must create a new list (containing new nodes, allocated on the heap) that contains the set intersection of the values in both lists. The part needed to be changed is in bold.

For example:

List 1: 0 1 2 List 2: 2 3 4 Union: 2 List 1: 0 2 2 2 List 2: 0 0 0 4 Union: 0 

The order of nodes in your new list does not matter, only that it is a proper union. A main function has been provided that tests your listIntersection function.

//main.cpp

#include

using namespace std;

struct node {

int val;

node *next;

};

void printList(node *head) {

if (head == NULL) {

cout << "Empty list" << endl;

return;

}

node *temp = head;

int count = 0;

while(temp != NULL) {

cout << "Node " << count << ": " << temp ->val << endl;

count++;

temp = temp->next;

}

}

node *listIntersection(node *first, node *second) {

// your code here

return NULL;

}

int main() {

// Example #1

node n_0, n_1, n_2, n_22, n_3, n_4;

n_0.val = 0;

n_1.val = 1;

n_2.val = 2;

n_22.val = 2;

n_3.val = 3;

n_4.val = 4;

n_0.next = &n_1;

n_1.next = &n_2;

n_2.next = NULL;

n_22.next = &n_3;

n_3.next = &n_4;

n_4.next = NULL;

cout<<"First List:"<

printList(&n_0);

cout<<"Second List:"<

printList(&n_22);

node *union1 = listIntersection(&n_0, &n_22);

cout<<"Intersection:"<

printList(union1);

cout<

// Example #2

node p00, p01, p02, p03, p10, p11, p12, p13;

// List 1: 0 2 2 2

p00.val = 0; p00.next = &p01;

p01.val = 2; p01.next = &p02;

p02.val = 2; p02.next = &p03;

p03.val = 2; p03.next = NULL;

// List 2: 0 0 0 4

p10.val = 0; p10.next = &p11;

p11.val = 0; p11.next = &p12;

p12.val = 0; p12.next = &p13;

p13.val = 4; p13.next = NULL;

cout<<"First List:"<

printList(&p00);

cout<<"Second List:"<

printList(&p10);

node *union2 = listIntersection(&p00, &p10);

cout<<"Intersection:"<

printList(union2);

cout<

return 0;

}