CareerCup

1) calculate the lengths of the two list, take n+m time.

2) assume n>=m, let the current elements of list1 and list2 are the heads, and then list 1 go to the (n-m)th element,

3) compare the current element , if matched, return current element, else let the current elements of two list be the next.

4) if ended, return null;

How about push these nodes into two stacks, after reaching the end, start to pop them. When the two top nodes are different, the one that just being popped out is the convergence node.

Using the head of 2nd LL, get the addr of first node. Then while traversing the 1st compare every nodes addr. If math found break

Also do the vice versa process

this is n square.

traverse L1, put each node address in an array A[1..n];
traverse L2, put each node address in another array B[1..m];
compare A[n-i] with B[m-i] (i=0..n or m), find where A[n-j]!=B[m-j]
if j==0, no merge
if j>0, merge at node address A[n-j+1]
O(m+n)

good one...anyone?
remember that the nodes of 2 LLs before the convergeence point neednt be the same...

well i posted this question

1 answer that i came across is

take 1 node at a time in 1st list. for each node traverse all nodes of 2nd list and compare.
if the two nodes converge there will be a match at some time, that is the node you need to return

I guess above solution is descent one.

else,
put the addresses of each node of LL1 in a hashtable.
when trying to put addresses of nodes of LL2 in the same hashtable, if there is collission, check if the same address exists, if yes that node is the point of convergence.

we could have 2 pointers.

curr1 pointing to the head node of the first list say head1 and similarly curr2 pointing to the head node of the second list.I wrote the following pseudo code,i guess this should work.

curr2=head2;
while(curr2!=NULL)
{
curr1=head1;
while(curr1!=Null)
{
if(curr1==curr2)
return curr1;
else
curr1=curr1->next;
}
curr2=curr2->next;
}
This way we ensure that each and every node in list 2 would be compared with every other node in list one the moment a match ..i.e convergence point is found the node would be returned.

What if 2 list split after merge?
This case should also be considered?

will the above solution work for these two lists?

1 2 3 4 5 6 7 8 9

1 2 5 4 6 6 7 8 9

how will they split after merging as the common node will be able to point to just one node...So after merging they will have common list..

->Take hash of all the addresses of L1

-> Start off with taking hash of address of each node in L2. If collision occurs compare the address. If addresses matches you get the common node.

-> Hashing function for L1 must be collision free for L1.

compare the sizes of both; - o(n)
take difference of them, say it k - o(1)
find the bigger list - o(1)
move the bigger list k times - o(n)
now move both the smaller and larger list one at a time -o(n)
For each comparison check whther they point to the same address -o(1)
if yes return the node and exit the function -

Total time complexity - o(n)

To Anonymous on February 16, 2009
will the above solution work for these two lists?

1 2 3 4 5 6 7 8 9

1 2 5 4 6 6 7 8 9

Here we are dealing with address locations so if if the two lists point to the same address where 1 is stored then there itself you would get the point of convergence.It would not move any further.However this could be considered as atest case and surround some peice of code to endsure that if the lists are typically the same then eithere they r one and the same list or say point of covergence is first node or throw some error message.

Reverse both the lists and traverse the lists simultaneously till they diverge.
Reversing should take O(m+n) and then traversing the lists should take O(m) or O(n) depending on which is smaller.

One downside of this solution is that the lists are reversed. If the original lists have to be preserved, we might have to reverse the lists again.

above solution wouldn't work since the moment 1 list is reversed the common node between other list and this list would be lost.

best way would be Ramsundar's .. in O(n) time

Node *listMergeNode(Node *head1,Node *head2)
{
if(!head1 || !head2) return NULL;
Node *list1 = head1;
Node *list2 = head2;

if(!list1->next || !list2->next) return NULL;

while(list1 && list2)
{
}
}

Node *listMergeNode(Node *head1,Node *head2)
{
if(!head1 || !head2) return NULL;
Node *list1 = head1;
Node *list2 = head2;

while(*list1 && *list2)
{
if(*list1 == *list2)
return list1; //we have found the merge

list1 = list1->next;
list2 = list2->next;
}
return NULL; // if we reach here we have reached end of 1 of the list and no elem was found
}

Node findCommon(Node h1, Node h2) {
    Stack s = new Stack();
    s.push(h1);
    while(h1 != null && h2!=null) {
        Node n = s.pop();
        if(n == h2) {
            return n;
        } else {
            s.push(n);
            h1 = h1.next();
            s.push(h1);
            h2 = h2.next();
        }
    }
    return null;

Following algo is m+n with no extra space.

If lists are allowed to be altered do the following -

1. Recursively reverse list 1
2. Transverse list 2. When you find a node with next pointer pointing at the node the node itself then you have the first node where the lists converge

find the length of both linklist l1 and l2. then take one extra variable X=l1-l2. after it traverse l1 increment by x. untill not found l1==l2

If you consider the tail of the lists as a root of a tree, and the heads as leaves, this is finding the first common ancestor of the given two leaves.

use one visit tag with each node like "TRAVERSED" and make it true or false accordingly in case we've to form it from initial.....traversal should be independent ....howz it?

the smartest answer was from bluetide...rest are just duplication of previous solutions...

mohit's solution is the real workable solution and bluetide is also good one

If we are not allowed to use any extra data structure, e.g, stack or hashtable, I guess the solution would be:
assume the common node is k th node counting from the tail, then, it is n-k + 1 and m-k+1 node counting from the head. Therefore, first reverse the first link link and point the head of the first link link (now the tail) to the head of the second link link. Starting count from the head of the second link link to see how many nodes it traverse to reach itself (as there is a loop), which should be n+m-2k+1. Hence, if we count n and m at the begining, we could compute k and starting from the tail, we can identify this command node.

1. traverse list1 till end and count elements (n1) (store last node ptr)
2. traverse list2 till end and count elements (n2)
3. compare last node of two lists it should be same. else no intersection
now let the common part of two lists have k nodes then
n1= number of different nodes of list1 (pre_n1) + k
n2= number of different nodes of list2 (pre_n2) + k
n1-n2 = prev_n1 - pre_n2
by traversing the smaller list by |prev_n1-prev_n2| i.e |n1-n2| nodes we will arrive at point of intersection.
complexity
o(n1)+o(n2)+o(|n1-n2|) ~ o(n)