Find the node where 2 lists merge

[anunaygupta]

Hello all,

I have a data structures problem.
Assume there are 2 linked lists L1 and L2. They merge into some node.

L1 1->2->3->4->5->6
/
L2 8->7->9->/

L1 and L2 merge in node with value 5. We need to return the pointer to
the node with value 5.
What is the best and efficient solution to find the node where the 2
lists merge?

Thanks,
Anunay

 

[Richard Heathfield]

(e-mail address removed) said:

Hello all,

I have a data structures problem.
Assume there are 2 linked lists L1 and L2. They merge into some node.

L1 1->2->3->4->5->6
/
L2 8->7->9->/

L1 and L2 merge in node with value 5. We need to return the pointer to
the node with value 5.
What is the best and efficient solution to find the node where the 2
lists merge?

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;
}
}

 

[anunaygupta]

Hi Richard,

Can you please explain me the logic of the above code?

Thanks,
Anunay

 

[Vladimir Oka]

(e-mail address removed) opined:

Hi Richard,

Richard who?

Can you please explain me the logic of the above code?

There's no code above.

Please quote context (what you're replying to, and who said it). Read
the link in my sig.

--
"Oh, I've seen copies [of Linux Journal] around the terminal room at
The Labs."
(By Dennis Ritchie)

<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>

 

[Vladimir Oka]

Vladimir Oka opined:

(e-mail address removed) opined:


Richard who?

Ooops.
Apologies.
Didn't think it'd sound like this. :-(

--
"Computers may be stupid, but they're always obedient. Well, almost
always."

-- Larry Wall (Open Sources, 1999 O'Reilly and Associates)

<http://clc-wiki.net/wiki/Introduction_to_comp.lang.c>

 

[Richard Heathfield]

[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:

(e-mail address removed) said:

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;
}
}

 

[Amit Bhatnagar]

Here's another solution that came to mind..
Not exactly very efficient, but i find it easy to think recursively...


struct node * commonnode( struct node * ptr1, struct node * ptr2)
{

struct node * common;

if (ptr1==ptr2)
/* Common node found.. This may be null too.. that meas actually no
common node */
return ptr1;

if (!ptr1 || !ptr2) return NULL ; /* If one of them is null, no chance
of having a common node*/

common = commonnode(ptr1->next, ptr2);
if (common) /* Some common node found */
return common;

return commonnode(ptr1,ptr2->next);

}

 

[CBFalconer]

Here's another solution that came to mind..
Not exactly very efficient, but i find it easy to think recursively...

You have already been told that you need to include context.
Without it your article is simply meaningless blather to most
readers. Google is not usenet, so act accordingly. See below for
means.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

 

[jitu.csewizard]

L1 1->2->3->4->5->6

/
L2 8->7->9->/

L1 and L2 merge in node with value 5. We need to return the pointer to
the node with value 5.
What is the best and efficient solution to find the node where the 2
lists merge?

one more solution is possible if the linked lists are read only and we
can't have a counter
traverse through L1..let its length be m+l (l is the length of common
part of the linked list)
similarly L2 has length n+l
subtract both you will get m-n
if it is positive L1 has m-n nodes more than L2
traverse these many nodes on L1.
now L1 and L2 has same number of nodes till end.
go on incrementing and comparing the nodes , you will get the point
where both the lists are merging

regards
jitendra.

 

[Amit Bhatnagar]

I could think of a better solution...
Its complexity is: O(length of longer list)
The funda is :
if lengths of both lists are equal, then we can just keep on moving
the pointers ptr1 and ptr2 and comparing them each time till we reach
a common node or null.

If the lengths are unequal, reduce the problem in terms of comparing
the list with equal number of nodes by moving the pointer to the longer
list till the number of nodes in the resulting lists are equal..

Here's some code for above logic:


struct node * commonnode( struct node * ptr1, struct node * ptr2)
{
int l1,l2;
l1=listlength(ptr1), ;
l2=listlength(ptr2);
/* calculating Length of a list is trivial; can be done in O(n) time
if n nodes are there*/

for (int i=0;i< l1-l2;i++)
ptr1=ptr1->next;

for (int i=0;i< l2-l1;i++)
ptr2=ptr2->next;
/* Moving the pointer to longer list till the length of remaining list
equals thatt of shorter list; above loops have no effect on shorter
list */

/* Now we have equal nodes in the lists pointed to by ptr1 and ptr2*/

while (ptr1 && ptr2) /*Continue as long as one of them is null*/
{
if (ptr1==ptr2)
return ptr1; /* Common node found.. */

ptr1=ptr1->next;
ptr2=ptr2->next;
}

/* No common node :-( Return NULL */
return NULL;
}