FOR FREE MATERIALS

The elements of the two lists are taken as input. The intersection is performed on the two given lists. Here, lists are represented using a singly linked list. A linked list is the collection of nodes. 

Each node of the list has two parts -

# Data Part

# Address Part

Let the two lists be:

And

The intersection of two lists contains the common elements of the two lists. For performing the intersection first a pointer ‘ptr’ points to the first node of the first list. 

Now, for each element of the first list pointed by the pointer ‘ptr’, a new pointer will point to the first node of the second list as:

First, the element of the first list (10) is compared with the data of the second list (10). As both the elements are the same that means this is a common element of these two lists. Then this element will be inserted into a new list pointed by ‘head_i’ which stores the intersection of two lists.

Now, the pointer ‘ptr’ will be moved to the next node of the first list.

Again, the same process will be repeated i.e. the second list will be searched for the element ‘15’. As the element is not found in the 2nd list then this element will be not inserted into the list pointed by the pointer ‘head_i’. 

The same process will be continued for the next two elements of the first list. After completing the intersection the result will be:

INPUT:  The number of elements to create the lists and the elements which are to be inserted.

OUTPUT:  
a) Two lists after creating it.
b) The list after performing the ‘intersection’ operation.

PROCESS:
Step 1: Define a structure named ‘node’ which has two parts−
The data part of integer type.
The ‘next’ (points to it’s next node i.e. the address of the next node) part which is a structure(node) type pointer.

Step 2: Create a function “node* createlist()”
 Step 2.1: Take the number of  elements from user in an ‘integer’ type variable ‘n’
 Step 2.2: For i=0 to (n-1) repeat  Step 2.3 to Step 2.7
 Step 2.3: Take the element which is to be inserted in an integer type variable  ‘x’.
 Step 2.4: Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.                    
 Set data[p] <- x
 Set next[p] <- Null
 Step 2.5: If (head = Null) then
 Set head1 <- p
 [End of ‘If’ ]
 Step 2.6: Else   
 Set next[ptr] <- p
 [End of ‘Else’] 

 Step 2.7: Set ptr <- p

 [End of  Step 2.2 ‘For’ loop]
 Step 2.8: return head
 [End of  the function “node* createlist( )”]   


Step 3: Create a function “void displaylist(node *head)”
  Step 3.1: Set p <- head
  Step 3.2: While(p≠Null) then repeat  Step 3.3 and Step 3.4
  Step 3.3: Print  data[p]
  Step 3.4: Set p <- next[p]	
   [End of  Step 3.2 ‘While’ loop]
   [End of  the function “void displaylist( )”]


Step 4: Create a function “node * intersection_list(node *h1,node *h2)”
 Step 4.1: Set headi<-null
 Step 4.2: Set ptr<-h1
 Step 4.3: while ptr≠NULL repeat step 4.4 to step 4.10
 Step 4.4: Set ptr2<-h2
 Step 4.5: Set c<-0
 Step 4.6: while ptr2≠NULL repeat step 4.7 to step 4.8
 Step 4.7: if data[ptr] =data[ptr2] then
		   Set c<-c+1
		   [End of step 4.7 ‘if’]
 Step 4.8: Set ptr2<-next[ptr2]
		   [End of step 4.6 ‘while’ loop]
 Step 4.9: if c≠0 then
  Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.                    
  Set data[p] <- data[ptr]
  Set next[p] <- Null
  If headi=NULL then
  Set headi<-p
	else
  Set next[ptr1]<-p
  [End of ‘if’]
  Set ptr1<-p
  [End of step 4.9 ‘if’]
  Step 4.10: Set ptr<-next[ptr]
  [End of step 4.3 ‘while’ loop]
  Step 4.11: Return headi
  [End of function ‘intersection_list(h1,h2)’]


Step 5: [Function ‘main()’]
  Call the function ‘createlist()’
  Call the function ‘displaylist(head)’
  Call the function ‘intersection_list(head1,head2)’

Step 6: Stop.