FOR FREE MATERIALS

The elements of two lists are taken as input. The union 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

In the case of union operation of two lists, all the elements of the two lists will be in the ‘union’ list but the common elements of the two lists will appear just ones in the ‘union’. To perform union operation first the elements of the first list will be copied to the new list pointed by the pointer ‘head_u’ where the union is to be stored. So, the list of the union will be: 

Now, a pointer ‘ptr’ will be pointing to the first node of the second list pointed by ‘head1’.

The full list pointed by the pointer ‘head_u’will be searched for the element pointed by ‘ptr’ i.e. ‘20’. As the data is already present in the list storing the ‘union’ then this element will not be inserted in the ‘union’ list. The pointer will be moved to the next node.

Again, the same process will be followed. The data pointed by ‘ptr’ will be compared with each element of the list pointed by ‘head_u’, as the data is already present in the union list then this data will also be skipped and the ‘ptr’ will be moved to the next node.

Now the same process will be continued and as the data (30) is not present in the list pointed by ‘head_u’ then the node with data (30) will be appended to the list pointed by the pointer ‘head_u’.

Therefore, the union of the two lists 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 ‘union’ 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 * union_list(node *h1,node *h2,int m,int n)”
	Step 4.1: Set headu<-null
 Step 4.2: Set ptr<-h1
  Step 4.3: for i=0 to m-1 repeat step 4.4 to step 4.7
 Step 4.4: Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.                    
  Set data[p] <- data[ptr]
  Set next[p] <- Null
 Step 4.5: if headu=NULL then
  Set headu<-p
	else
	Set next[ptr1]<-p
 [End of step 3.5 ‘if']
  Step 4.6: Set ptr1<-p
  Step 4.7: Set ptr<-next[ptr]
  [End of step 4.3 ‘for’ loop]
  Step 4.8: Set ptr<-h2
  Step 4.9: while ptr≠NULL repeat step 4.10 to step 4.16
  Step 4.10: Set ptr2<-headu
  Step 4.11: Set c<-0
  Step 4.12: while ptr2≠NULL repeat step 4.13 to 4.14
  Step 4.13: if data[ptr] =data[ptr2]
	 Set c<-c+1
  [End of step 4.13 ‘if’]
  Step 4.14: Set ptr2<-next[ptr2]
  [End of step 4.12 ‘while’ loop]
  Step 4.15: 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
   Set next[ptr1]<-p
   Set ptr1<-p
  [End of step 4.15 ‘if’]
  Step 4.16: Set ptr<-next[ptr]
  [End of 4.9 ‘while’ loop]
  Step 4.17: Return headu
  [End of function ‘union_list(head1,head2,m,n)’]

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

Step 6: Stop.