Write a function to get the intersection point of two Linked Lists
- Intersection point means end of one linked list is linked with some node in another linked list.
Given two Linked Lists, create intersection lists that contain intersection of the elements present in the given lists.
Example
[pastacode lang=”markdown” manual=”Input%3A%0A%20%20%20List1%3A%2020-%3E25-%3E4-%3E30%0A%20%20%20lsit2%3A%20%208-%3E4-%3E2-%3E20%0AOutput%3A%0A%20%20%20Intersection%20List%3A%204-%3E20″ message=”” highlight=”” provider=”manual”/]Sample Code in C:
[pastacode lang=”c” manual=”%2F%20C%20program%20to%20get%20intersection%20point%20of%20two%20linked%20list%20%20%0A%23include%3Cstdio.h%3E%20%0A%23include%3Cstdlib.h%3E%20%0A%20%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20Node%20%0A%7B%20%0A%20%20int%20data%3B%20%0A%20%20struct%20Node*%20next%3B%20%0A%7D%3B%20%0A%20%20%0A%2F*%20Function%20to%20get%20the%20counts%20of%20node%20in%20a%20linked%20list%20*%2F%0Aint%20getCount(struct%20Node*%20head)%3B%20%0A%20%20%0A%2F*%20function%20to%20get%20the%20intersection%20point%20of%20two%20linked%20%0A%20%20%20lists%20head1%20and%20head2%20where%20head1%20has%20d%20more%20nodes%20than%20%0A%20%20%20head2%20*%2F%0Aint%20_getIntesectionNode(int%20d%2C%20struct%20Node*%20head1%2C%20struct%20Node*%20head2)%3B%20%0A%20%20%0A%2F*%20function%20to%20get%20the%20intersection%20point%20of%20two%20linked%20%0A%20%20%20lists%20head1%20and%20head2%20*%2F%0Aint%20getIntesectionNode(struct%20Node*%20head1%2C%20struct%20Node*%20head2)%20%0A%7B%20%0A%20%20int%20c1%20%3D%20getCount(head1)%3B%20%0A%20%20int%20c2%20%3D%20getCount(head2)%3B%20%0A%20%20int%20d%3B%20%0A%20%20%0A%20%20if(c1%20%3E%20c2)%20%0A%20%20%7B%20%0A%20%20%20%20d%20%3D%20c1%20-%20c2%3B%20%0A%20%20%20%20return%20_getIntesectionNode(d%2C%20head1%2C%20head2)%3B%20%0A%20%20%7D%20%0A%20%20else%0A%20%20%7B%20%0A%20%20%20%20d%20%3D%20c2%20-%20c1%3B%20%0A%20%20%20%20return%20_getIntesectionNode(d%2C%20head2%2C%20head1)%3B%20%0A%20%20%7D%20%0A%7D%20%0A%20%20%0A%2F*%20function%20to%20get%20the%20intersection%20point%20of%20two%20linked%20%0A%20%20%20lists%20head1%20and%20head2%20where%20head1%20has%20d%20more%20nodes%20than%20%0A%20%20%20head2%20*%2F%0Aint%20_getIntesectionNode(int%20d%2C%20struct%20Node*%20head1%2C%20struct%20Node*%20head2)%20%0A%7B%20%0A%20%20int%20i%3B%20%0A%20%20struct%20Node*%20current1%20%3D%20head1%3B%20%0A%20%20struct%20Node*%20current2%20%3D%20head2%3B%20%0A%20%20%0A%20%20for(i%20%3D%200%3B%20i%20%3C%20d%3B%20i%2B%2B)%20%0A%20%20%7B%20%0A%20%20%20%20if(current1%20%3D%3D%20NULL)%20%0A%20%20%20%20%7B%20%20return%20-1%3B%20%7D%20%0A%20%20%20%20current1%20%3D%20current1-%3Enext%3B%20%0A%20%20%7D%20%0A%20%20%0A%20%20while(current1%20!%3D%20%20NULL%20%26%26%20current2%20!%3D%20NULL)%20%0A%20%20%7B%20%0A%20%20%20%20if(current1%20%3D%3D%20current2)%20%0A%20%20%20%20%20%20return%20current1-%3Edata%3B%20%0A%20%20%20%20current1%3D%20current1-%3Enext%3B%20%0A%20%20%20%20current2%3D%20current2-%3Enext%3B%20%0A%20%20%7D%20%0A%20%20%0A%20%20return%20-1%3B%20%0A%7D%20%0A%20%20%0A%2F*%20Takes%20head%20pointer%20of%20the%20linked%20list%20and%20%0A%20%20%20returns%20the%20count%20of%20nodes%20in%20the%20list%20*%2F%0Aint%20getCount(struct%20Node*%20head)%20%0A%7B%20%0A%20%20struct%20Node*%20current%20%3D%20head%3B%20%0A%20%20int%20count%20%3D%200%3B%20%0A%20%20%0A%20%20while%20(current%20!%3D%20NULL)%20%0A%20%20%7B%20%0A%20%20%20%20count%2B%2B%3B%20%0A%20%20%20%20current%20%3D%20current-%3Enext%3B%20%0A%20%20%7D%20%0A%20%20%0A%20%20return%20count%3B%20%0A%7D%20%0A%20%20%0A%2F*%20IGNORE%20THE%20BELOW%20LINES%20OF%20CODE.%20THESE%20LINES%20%0A%20%20%20ARE%20JUST%20TO%20QUICKLY%20TEST%20THE%20ABOVE%20FUNCTION%20*%2F%0Aint%20main()%20%0A%7B%20%0A%20%20%2F*%20%0A%20%20%20%20Create%20two%20linked%20lists%20%0A%20%20%0A%20%20%20%201st%203-%3E6-%3E9-%3E15-%3E30%20%0A%20%20%20%202nd%2010-%3E15-%3E30%20%0A%20%20%0A%20%20%20%2015%20is%20the%20intersection%20point%20%0A%20%20*%2F%0A%20%20%0A%20%20struct%20Node*%20newNode%3B%20%0A%20%20struct%20Node*%20head1%20%3D%20%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20Node*)%20malloc(sizeof(struct%20Node))%3B%20%0A%20%20head1-%3Edata%20%20%3D%2010%3B%20%0A%20%20%0A%20%20struct%20Node*%20head2%20%3D%20%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20Node*)%20malloc(sizeof(struct%20Node))%3B%20%0A%20%20head2-%3Edata%20%20%3D%203%3B%20%0A%20%20%0A%20%20newNode%20%3D%20(struct%20Node*)%20malloc%20(sizeof(struct%20Node))%3B%20%0A%20%20newNode-%3Edata%20%3D%206%3B%20%0A%20%20head2-%3Enext%20%3D%20newNode%3B%20%0A%20%20%0A%20%20newNode%20%3D%20(struct%20Node*)%20malloc%20(sizeof(struct%20Node))%3B%20%0A%20%20newNode-%3Edata%20%3D%209%3B%20%0A%20%20head2-%3Enext-%3Enext%20%3D%20newNode%3B%20%0A%20%20%0A%20%20newNode%20%3D%20(struct%20Node*)%20malloc%20(sizeof(struct%20Node))%3B%20%0A%20%20newNode-%3Edata%20%3D%2015%3B%20%0A%20%20head1-%3Enext%20%3D%20newNode%3B%20%0A%20%20head2-%3Enext-%3Enext-%3Enext%20%20%3D%20newNode%3B%20%0A%20%20%0A%20%20newNode%20%3D%20(struct%20Node*)%20malloc%20(sizeof(struct%20Node))%3B%20%0A%20%20newNode-%3Edata%20%3D%2030%3B%20%0A%20%20head1-%3Enext-%3Enext%3D%20newNode%3B%20%0A%20%20%0A%20%20head1-%3Enext-%3Enext-%3Enext%20%3D%20NULL%3B%20%0A%20%20%0A%20%20printf(%22%5Cn%20The%20node%20of%20intersection%20is%20%25d%20%5Cn%22%2C%20%0A%20%20%20%20%20%20%20%20%20%20getIntesectionNode(head1%2C%20head2))%3B%20%0A%20%20%0A%20%20getchar()%3B%20%0A%7D%20″ message=”” highlight=”” provider=”manual”/]Code Explanation :
- Get count of the nodes in the first list, let count be c1.
- Get count of the nodes in the second list, let count be c2.
- Get the difference of counts d = abs (c1 – c2)
- Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
- Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)
Time Complexity: O(m+n)
Auxiliary Space: O(1)
Output :
The node of intersection is 15