CareerCup

Can you use recursion while unwinding? Recursively reach end of both lists. Then when you unwind the recursion check the pointers. At the point where the merge you would get the same pointer.

Nice requirement :) most probably impossible to meet, but you can try some not-very clever but working solutions, like get the next item on list-2 and search if this pointer is in list-1 (if found, this is a merging point). Surely works and it is a trivial solution. At least this is what I'd told him/her.

This is not a good solution at all, the interviewer did not want this because everybody tells the same, you should have told some other approach. You can even use the HashSet to do this very efficiently, You can use the negation technique, you can use slow and fast pointer technique..!!!

traverse the two given linked lists and compare the value of next of two the nodes in both link lists.
node *findMergeNode(node *head1, node *head2)
{
node *p=head1->next;
node *q=head2->next;

while(p!=NULL && q!=NULL)
{
if(p==q)
{
break;
}else
{
p = p->next;
q = q->next;
}
}
}
if(p==q)
{
return p->next;
}

Memory : O((n1+n2)*sizeof(Node* pointer)) ~ O(n)
Time : O(n1+n2+min(n1,n2)) ~O(n)

#include<stack>
int main()
{
    Node * head1 = list1;
    Node * head2 = list2;
    stack<Node*> s1,s2;
    while(head1)
    {
         s1.push(head1);
         head1 = head1->next;
    }
    while(head2)
    {
         s2.push(head2);
         head2 = head2->next;
    }
    while( !(s1.empty()) && !(s2.empty()) )
    {
            if(s1.top()  == s2.top())   
            {  cout<<"Lists intercept";
               break;
             }
            s1.pop();s2.pop();
    }



}

Does that seem correct ??

->reverse the two linked lists..take two pointers catering to both the linked lists
->start from the last node (which is now the head for both)..
->if both their head values are unequal..simply return (as they have no common intersection point)
->else keep on traversing both the linked lists.also maintain a prev pointer..
->just when you get the data values of both the pointers as different..break out of the loop and return the prev pointer bnode

Store the first linked list in hash with key as the value in the linked list..
when traversing the second linked ,chek first with the key matching.
if the key is matching then chek for address.

at the intersection point both the value should match.
ofcourse this method will take o(n) space complexity.
but i guess it is fine to give methods when the interviewer want to check our problem solving in different approach..

push the elements of the first linked list in to the stack.
now traverse the second linked list till the end.
when returning from the end pop an element from the stack and compare till the point both are unequal.
if there reach unequal point , ur previous crossed node is the intersection point.
ofcourse this method will take o(n) space , but it will give the interviewer that u r thinking differently i feel.

push the elements of the first linked list in to the stack.
now traverse the second linked list till the end.
when returning from the end pop an element from the stack and compare till the point both are unequal.
if there reach unequal point , ur previous crossed node is the intersection point.
ofcourse this method will take o(n) space , but it will give the interviewer that u r thinking differently i feel.

1. Find the lengths of each list -> O(n)
2. Find the difference and traverse that many nodes in larger list (p1)
With the other pointer at the beginning of the smaller list (p2), these are at equal distances form the pt of intersection. Increment both till they meet at the intersection (they will surely meet as they are at equal distance from the intersection. -> O(n)

The interviewer is a moron.

Btree can be used to solve this problem. make the addresses of the first linked list to be the node val of the binary tree. In this way create the first binary tree with the first linked list. Then use the second linked list address to scan the first btree node values. when it matches, it means the merging point.