[Sorry to reply to my own article, but an explanation of the logic of my
code has been requested. First, the problem statement (abbrev'd).]
Richard Heathfield said:
an*********@gmail.com said:
What is the best and efficient solution to find the node where the 2
lists merge?
We will have two pointers, and start them off at the beginnings of the two
branches. If the branches merge, we need a pointer to one or other of them.
We begin by assuming that each list is terminated by a null pointer, and
that every node on each list has an int field, count, which is initially
set to 0. If you like, think of it as being unpainted. If, during our
travels, our first pointer hits it, we'll add 1 to it (paint it blue). If
our second pointer hits it, we'll add 1 to it (paint it yellow). If, after
such an addition, the count value is 2 (painted blue+yellow=green), we have
just been processing a node that is in both lists. Since we have not yet
encountered such a node, this must be the first merge point.
So imagine two paintbrushes, each one travelling down its own branch of the
list, one painting a blue stripe and the other painting a yellow stripe. As
soon as we detect green, we stop, and our paintbrush is hovering right over
the merge point.
Here is the code again:
mergenode = 0;
while(l1 && l2 && mergenode == 0)
{
++l1->count;
++l2->count;
if(l1->count == 2)
{
mergenode = 1; /* l1 points to node at merge point */
}
else if(l2->count == 2)
{
mergenode = 2; /* l2 points to node at merge point */
}
else
{
l1 = l1->next;
l2 = l2->next;
}
}
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)