Interview Question
Country: India
I am not sure how your logic would work in case there is no difference of length . And also you need to move the pointer K+1 time to get to the merged node. Correct me if I am wrong
How abt this
Use an hashmap to store the address of each node with address as key and node->data as value.
Now start iterating from head of each list. Store the address of both the head ptrs . So the smaller list will reach the merge point earlier .In each iteration check whether such an address exist in the hashmap. If yes they merge at that point .
Though it will take more k space but cant think of any other solution :(
I guess following will work:
- Anurag Singh December 15, 2011Here k should be some given no say, 5 or 10 and this is the difference of the length of two linked lists. So both lists will make a Y shape where one list has K node more than the other one. Here traversing complete list is not allowed so we can't find which list is longer one (If allowed, traverse K node 1st one longer list, then traverse both list together node by node and keep checking if they are same which will be the merged node)
So we need to try this on both list together where we can have two pairs of pointers say P1, P2 and Q1, Q2 (P1, Q1 pointing to one list and P2, Q2 pointing two another).
1. Move P1 and P2 upto K nodes
2. Now move all 4 pointers node by node, keep comparing equality on P1, Q2 and P2, Q1. One pair will point to merged node when they reach node p and that will give the answer.