Take two linked lists L1 and L2 with m and n number of nodes.If they intersect and merge from some node.Now we need to find the node where they got intersected.
Algorithm1 :
Traverse each linked list and store the address of visited node in hash.Now traverse the second linked list and if you see any address already existed in hash then return this node.In this process,no need to alter linked lists.It works in O(m+n).
Algorithm2:
1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) 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.
5) 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)
Refer for coding : http://geeksforgeeks.org/?p=2405
Algorithm1 :
Traverse each linked list and store the address of visited node in hash.Now traverse the second linked list and if you see any address already existed in hash then return this node.In this process,no need to alter linked lists.It works in O(m+n).
Algorithm2:
1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) 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.
5) 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)
Refer for coding : http://geeksforgeeks.org/?p=2405
No comments:
Post a Comment