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