Interview Question
Country: India
Can you please give an example? The way I understand this question is these list will have diff values and one of the memory pointer will be same and that is where it is intersecting.
They meet at a point and after that they are same,means they share common tail.
1->2->3->7->8->9
4->5->6--^
I guess you're technically not traversing the linked lists twice in this approach, but you're traversing the data twice.
- Traverse the first list inserting each element into a hash table
- Traverse the second looking up each node in the hash table, if it exists, add it to the result
O(n+m) time - traverse each list once
O(max(n,m)+sizeof_intersection) space - extra hash table + result list
n,m are the sizes of each list
Yep. In fact, this is really the only efficient way to solve the problem if you can't even obtain something as basic as the length of the linked lists before traversing.
Yes hashing seems to be a right approach. Other approaches traverse the lists more than once.
Although when you use hashing, you're looking at some of the data more than once too...whenever you hash a node for lookup in the table, you're comparing it to hashes of nodes already in that bucket. So you can end up looking at the hashes of the nodes already in a bucket multiple times, which is indirectly a way of making multiple passes over data. It's not really any better than copying the data over to an array and doing a backwards traversal to find the point of divergence, like recommended in the other solution.
You are assuming that each node will have distinct values, which may not always be the case.
Blahfoo, Good Answer !
I have another approach where I don't need any other memory -
1. count elements of each list,
2. find length diff
3. traverse smaller list from beginning and longer list after diff number of elements from begining.
4. compare both pointer while traversing both together. If equal, that is the merge point.
In this case you will traversing more than once. Condition is that you should travers only once.
I think, Intersection means meeting the 2 linked lists at one point (one node), where the two nodes meeting at one node (having same next pointer of that meeting node).
Lets say, a node having a data & next pointer. Checking the next pointer of List1 with next pointer of List2 are same, while traversing in the two lists. If they are same, that node is called intersection node (intersection point).
meetingpoint(Node* n1, Node*n2)
{
Node *mnode = NULL;
if(!n1->next && !n2->next)
return NULL;
if(!n1->next)
mnode = meetingpoint(n1, n2-.>next);
else if(!n2-.next)
mnode = meetingpoint(n1->next, n2-.>next);
else
mnode = meetingpoint(n1->next, n2->next);
if(mnode)
return mnode;
else if(n1 == n2)
return NULL;
else
return n1->next;
}
Traverse each list and push contents into stacks S1 and S2.
- Blahfoo March 30, 2012Pop each stack until you find dissimilar elements and return the last same element.