The following algorithm traversals both lists twice to find the
intersection point, without modification to the original nodes.
The only assumptions:
1) Head pointer of two list: La, Lb
2) .next point to the next node.
3) .next of the tail node is NULL
intersect(La,Lb)
{
// Find the length difference of two lists
for (pA = La, pB = Lb; pA != NULL && pB != NULL; pA = pA->next, pB =
pB->next);
// Discard the beginning of the longer list, to get equal length as
the shorter one.
if(pA != NULL) {
for(pC = pA, pA = La; pC != NULL; pA = pA->next, pC = pC->next);
pB = Lb;
} else if(pB != NULL) {
for(pC = pB, pB = Lb; pC != NULL; pB = pB->next, pC = pC->next);
pA = La;
}
// Traversal both list, until we get a common node, return this node.
// If no such intersection, NULL is returned. (pA,pB will get NULL at
the same time)
for( ; pA != pB; pA = pA->next, pB = pB->next);
return pA;
}
On 2010-9-15 15:50, sharad kumar wrote:
you dont have the structure of the node
typedef struct member node
{
int data;
struct member * next;
}ll;
On Tue, Sep 14, 2010 at 5:57 PM, soundar <[email protected]
<mailto:[email protected]>> wrote:
From first linked list set flag value in each traversal of
node......then start from second linked list suppose if flag value is
already set that is the intersection point
correct me if i am wrong
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
<mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto:algogeeks%[email protected]>.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
