Menu
This question may be old, but I couldn't think of an answer.
Say, there are two lists of different lengths, merging at a point; how do we know where the merging point is?
Conditions:
867
Have a visited flag with each node. Traverse the first linked list and keep marking visited nodes. Now traverse the second linked list, If you see a visited node again then there is an intersection point, return the intersecting node.
A simple solution is to consider each node of the first list and check if it can be reached from the second list. The first node in the first list that is reachable from the second list is the intersection point.
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.
The following is by far the greatest of all I have seen - O(N), no counters. I got it during an interview to a candidate S.N. at VisionMap.
Make an interating pointer like this: it goes forward every time till the end, and then jumps to the beginning of the opposite list, and so on. Create two of these, pointing to two heads. Advance each of the pointers by 1 every time, until they meet. This will happen after either one or two passes.
I still use this question in the interviews - but to see how long it takes someone to understand why this solution works.
90
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
