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.
TIME COMPLEXITY
The time complexity of performing the union of two linked lists is O(m * n) where m is the number of elements of the first list and n is the number of elements of the second list.
If both the numbers are considered to be equal then,
SPACE COMPLEXITY
The space complexity of this program is O(m + n) where m is the number of elements of the first list and n is the number of elements of the second list.
If both the numbers are considered to be equal then,
Related
Contributed by