CareerCup

- Push all the nodes into 2 different stacks.
- Then pop once from both stacks to check if the nodes are same,
- - if so continue popping till the nodes differ.
- - else there are no common nodes

If there is a common node between two link lists, then their last nodes should be same. Just compare the last node of both the link lists.

If there is a common code, then it shd look like a 'Y'. So first go thru both linked list to find their lengths in O(n). Get the difference between length, say d.
say, head1 and head2 are pointers to linkedlists
scan thru the list :
compare head1->value == (head2+d)->value

total is O(n) time

Traverse LL1. At its end add a nodeZ.
Then traverse LL2. If there is a common node, then the nodeZ will be found at the end of LL2

@adiva
your idea is good.. but i need to traverse LL1 once and place the node.. then traverse LL2 and in case if the list merges, I will have to traverse thru them again. Isn't there any way where I can finish off the traversal and simultaneously check for common node??

I like the idea with the stacks. :) But you can make it for O(n) memory I believe:
bool CommonNode(List* aList, List* bList)
{
List* a = aList, *b = bList;
while( (a != NULL) && (b != null) )
{
if(a == b)
return true;
a = a->pNext;
b = b->pNext;
}
return false;
}

A valid improvement of the algorithm will be if you make step equal to a = a->pNext->pNext. Or even more, but this requires more chechs to not going read from null.

All we need to do is to first calculate len=len1-len2 (len1>len2, as discussed above). Point p1 and p2 to list1 (the longer one) and list2 respectively. Then step only p1 for "len" no. of nodes. After this we are guaranteed that p1 and p2 are equidistant from the common node. So now start stepping p1 and p2 simultaneously until p1==p2. This will the common node. This is a simple O(n) solution.

use recursive we can make it with o(n) time, only one transverse needed.

int commomNode(list* p1, listp2) {
if (p1 == NULL && p2 == NULL)
return 0;
else if (p1 == NULL)
return commomNode(p1,p2->next);
else if (p2 == NULL)
return comonNode(p1->next,p2);
else
return commonNode(p1->next,p2->next);

if (p1 == p2)
return 1;
else
return 0;
}
}

the algorithm of finding differences in lengths will not work since the first node itself can be the common node.

@lensbo
it's entirely wrong!
it simply traverses till end...

@lensbo
it's entirely wrong!
it simply traverses till end...

if it is forwaded singly linked list, just get the last node of one of the LL and compare with each node of other.

Say L1 - A->B->C->D->E->F->G->H
L2 - K->L->M->G->H OR K->L->M->N->O->P

Take H node from L1 and compare with each node in L2.

only the last one is correct.

If there is a common node between two link lists, then their last nodes should be same. Just compare the last node of both the nodes.

I was thinking if we need to search the common element then can we do it faster than O(n*n) any ideas of a better complexity algorithm to find the common element?

The answer given by Anonymous on December 26, 2008 is correct.
Just one flaw, what if the linked list is a circular list. The algorithm fails
eg First Linked List A->B->C->D->C
Second Linked List Z->Y->C->D->C
To solve this have another data member in each node. Set the data member to 1 when we visit for the first time during First Linked List traversal.
When we traverse the second linked list, check if any node has the data member set to 1.