COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

• Email
• Follow

```Hi,

Is there any efficient way of finding the intesection point of two
I mean to say that, there are two singly linked lists and they meet at
some point. I want to find out the addres of the node where the two

thanks for any help...

```
 0
Reply junky_fellow (377) 1/22/2008 7:19:46 AM

See related articles to this posting

```<junky_fellow@yahoo.co.in> wrote in message
> Hi,
>
>    Is there any efficient way of finding the intesection point of two
> I mean to say that, there are two singly linked lists and they meet at
> some point. I want to find out the addres of the node where the two
>
> thanks for any help...

you mean point of merge of linked list ? i cannot imaging "intersection" of

p  = listA;
q =  listB;

while(p && q) {
if(p->next == q->next) break;
p = p->next;
q = q->next;
}

if(p && q && (p->next == q->next))
{
printf("Merging point found\n");
}

But careful: I have not tested the code !

```
 0
Reply ravishankar.s (52) 1/22/2008 8:49:37 AM

```Ravishankar S said:

<snip>

> you mean point of merge of linked list ? i cannot imaging "intersection"
>
> p  = listA;
> q =  listB;
>
> while(p && q) {
>     if(p->next == q->next) break;
>     p = p->next;
>     q = q->next;
> }
>
> if(p && q && (p->next == q->next))
> {
>     printf("Merging point found\n");
> }
>
> But careful: I have not tested the code !

listA: A -- B -- C -- D
\
E -- F -- G
/
listB:           H -- I

You compare A with H, B with I, C with E, D with F, E with G. Now the loop
stops, and q is NULL. You missed the merge point completely.

I believe this has to be done in two nested loops (or at least, "as if" it
were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
be delighted to be proved wrong.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
```
 0
Reply rjh (10790) 1/22/2008 9:42:36 AM

```Richard Heathfield <rjh@see.sig.invalid> writes:

> Ravishankar S said:
>
> <snip>
>
> > you mean point of merge of linked list ? i cannot imaging "intersection"
> >
> > p  = listA;
> > q =  listB;
> >
> > while(p && q) {
> >     if(p->next == q->next) break;
> >     p = p->next;
> >     q = q->next;
> > }
> >
> > if(p && q && (p->next == q->next))
> > {
> >     printf("Merging point found\n");
> > }
> >
> > But careful: I have not tested the code !
>
> Indeed. Consider these linked lists:
>
> listA: A -- B -- C -- D
>                        \
>                         E -- F -- G
>                        /
> listB:           H -- I
>
> You compare A with H, B with I, C with E, D with F, E with G. Now the loop
> stops, and q is NULL. You missed the merge point completely.
>
> I believe this has to be done in two nested loops (or at least, "as if" it
> were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
> be delighted to be proved wrong.

You can do O(listAnodecount+listBnodecount) if you accept to allocate
memory in O(listAnodecount+listBnodecount) as well: build reversed lists
referencing the original and then iterate on them until they diverge.

--
Jean-Marc
```
 0
Reply jm749 (344) 1/22/2008 9:50:53 AM

```On Jan 22, 9:42 am, Richard Heathfield <r...@see.sig.invalid> wrote:
> Ravishankar S said:
>
> <snip>
>
>
>
> > you mean point of merge of linked list ? i cannot imaging "intersection"
>
> > p  = listA;
> > q =  listB;
>
> > while(p && q) {
> >     if(p->next == q->next) break;
> >     p = p->next;
> >     q = q->next;
> > }
>
> > if(p && q && (p->next == q->next))
> > {
> >     printf("Merging point found\n");
> > }
>
> > But careful: I have not tested the code !
>
> Indeed. Consider these linked lists:
>
> listA: A -- B -- C -- D
>                        \
>                         E -- F -- G
>                        /
> listB:           H -- I
>
> You compare A with H, B with I, C with E, D with F, E with G. Now the loop
> stops, and q is NULL. You missed the merge point completely.
>
> I believe this has to be done in two nested loops (or at least, "as if" it
> were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
> be delighted to be proved wrong.

Not proving you wrong, but let me remark that for a doubly linked list
the problem becomes trivial in case the linked lists do not contain
cycles: simply start at the end of both lists. For singly linked lists
this solution can be mimicked if one allows the use of malloc (or
constructing a singly linked list that goes the other way). I think
this solution can be extended to the cycle case with some care and
administration, but for now I'll just consider the problem somewhat
underspecified.

Stijn
```
 0
Reply micans (36) 1/22/2008 9:55:05 AM

```<junky_fellow@yahoo.co.in> wrote in message
>   Is there any efficient way of finding the intesection point of two
> I mean to say that, there are two singly linked lists and they meet at
> some point. I want to find out the addres of the node where the two
>
> thanks for any help...
>
struct node
{
struct node *next;
void *data;
int flag;
}

Iterate from start one to then end setting all the flags.
Iterate from start two. When you find a set flag, that's your merge point.

Horrid hack.
For some reason we cannot carry a flag about. So reverse the bits of the
next pointer. Almost always you will be able to detect a bit-reversed
pointer. You keep the start of list one and go through for a second time,
undoing your bit mangling. Needless to say, the horrid hack is dangerous.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

```
 0
Reply regniztar (3128) 1/22/2008 10:19:49 AM

```micans@gmail.com wrote:

>> listA: A -- B -- C -- D
>>                        \
>>                         E -- F -- G
>>                        /
>> listB:           H -- I
>>
>> You compare A with H, B with I, C with E, D with F, E with G. Now the loop
>> stops, and q is NULL. You missed the merge point completely.
>>
>> I believe this has to be done in two nested loops (or at least, "as if" it
>> were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
>> be delighted to be proved wrong.
>
> Not proving you wrong, but let me remark that for a doubly linked list
> the problem becomes trivial

....insofar as the above constellation couldn't occur in doubly-linked
lists. What would the "previous" pointer of E point to?

robert
```
 0
Reply boblatest2 (238) 1/22/2008 10:23:48 AM

```On Jan 22, 10:23 am, Robert Latest <boblat...@yahoo.com> wrote:
> mic...@gmail.com wrote:
> >> listA: A -- B -- C -- D
> >>                        \
> >>                         E -- F -- G
> >>                        /
> >> listB:           H -- I
>
> >> You compare A with H, B with I, C with E, D with F, E with G. Now the loop
> >> stops, and q is NULL. You missed the merge point completely.
>
> >> I believe this has to be done in two nested loops (or at least, "as if" it
> >> were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd
> >> be delighted to be proved wrong.
>
> > Not proving you wrong, but let me remark that for a doubly linked list
> > the problem becomes trivial
>
> ...insofar as the above constellation couldn't occur in doubly-linked
> lists. What would the "previous" pointer of E point to?
>
> robert

Indeed :( time for coffee ..

Stijn
```
 0
Reply micans (36) 1/22/2008 10:32:25 AM

```On Jan 22, 3:19=A0pm, "Malcolm McLean" <regniz...@btinternet.com> wrote:
> <junky_fel...@yahoo.co.in> wrote in message
> > =A0 Is there any efficient way of finding the intesection point of two
> > singly linked lists ?
> > I mean to say that, there are two singly linked lists and they meet at
> > some point. I want to find out the addres of the node where the two
>
> > thanks for any help...
>
> struct node
> {
> =A0 =A0struct node *next;
> =A0 =A0void *data;
> =A0 =A0 int flag;
>
> }
>
> Iterate from start one to then end setting all the flags.
> Iterate from start two. When you find a set flag, that's your merge point.=

>
In fact, I also thought of similar kind of solution, but there need
not be a flag in the node structure. I also thought of using the
padding bytes inserted in between the members of a structure and put
some pattern in the padding/unused bytes each time a node is
traversed. But, there may not be any padding bytes at all.
```
 0
Reply junky_fellow (377) 1/22/2008 10:49:21 AM

```junky_fellow@yahoo.co.in wrote:

> On Jan 22, 3:19�pm, "Malcolm McLean" <regniz...@btinternet.com> wrote:
>> <junky_fel...@yahoo.co.in> wrote in message
>> > Is there any efficient way of finding the intesection point of two
>> > singly linked lists ?
>> > I mean to say that, there are two singly linked lists and they meet
>> > at some point. I want to find out the addres of the node where the
>>
>> > thanks for any help...
>>
>> struct node
>> {
>> struct node *next;
>> void *data;
>> int flag;
>>
>> }
>>
>> Iterate from start one to then end setting all the flags.
>> Iterate from start two. When you find a set flag, that's your merge
>> point.
>>
> In fact, I also thought of similar kind of solution, but there need
> not be a flag in the node structure. I also thought of using the
> padding bytes inserted in between the members of a structure and put
> some pattern in the padding/unused bytes each time a node is
> traversed. But, there may not be any padding bytes at all.

In addition, padding bytes need not retain their values after a write.
In fact, I think an attempt to write to them at all invokes undefined
behaviour.

```
 0
Reply santosh.k83 (3969) 1/22/2008 11:08:47 AM

```On Jan 22, 4:08=A0pm, santosh <santosh....@gmail.com> wrote:
> junky_fel...@yahoo.co.in wrote:
> > On Jan 22, 3:19=A0pm, "Malcolm McLean" <regniz...@btinternet.com> wrote:=

> >> <junky_fel...@yahoo.co.in> wrote in message
> >> > Is there any efficient way of finding the intesection point of two
> >> > singly linked lists ?
> >> > I mean to say that, there are two singly linked lists and they meet
> >> > at some point. I want to find out the addres of the node where the
> >> > two linked intersect.
>
> >> > thanks for any help...
>
> >> struct node
> >> {
> >> struct node *next;
> >> void *data;
> >> int flag;
>
> >> }
>
> >> Iterate from start one to then end setting all the flags.
> >> Iterate from start two. When you find a set flag, that's your merge
> >> point.
>
> > In fact, I also thought of similar kind of solution, but there need
> > not be a flag in the node structure. I also thought of using the
> > padding bytes inserted in between the members of a structure and put
> > some pattern in the padding/unused bytes each time a node is
> > traversed. But, there may not be any padding bytes at all.
>
> In addition, padding bytes need not retain their values after a write.
> In fact, I think an attempt to write to them at all invokes undefined
> behaviour

Santosh, Can you please tell me why the padding bytes need not retain
their values after a write ? Also, you wrote that writing to padding
bytes may invoke undefined behaviour. Why is it so ? I could not think
of any reason for that. Can you please tell me the reason behind it.
```
 0
Reply junky_fellow (377) 1/22/2008 11:35:27 AM

```"Malcolm McLean" <regniztar@btinternet.com> wrote in message
news:MvednTGsOIqlXgjanZ2dnUVZ8vOdnZ2d@bt.com...
>
> <junky_fellow@yahoo.co.in> wrote in message
> >   Is there any efficient way of finding the intesection point of two
> > singly linked lists ?
> > I mean to say that, there are two singly linked lists and they meet at
> > some point. I want to find out the addres of the node where the two
> >
> > thanks for any help...
> >
> struct node
> {
>    struct node *next;
>    void *data;
>     int flag;
> }
>
> Iterate from start one to then end setting all the flags.
> Iterate from start two. When you find a set flag, that's your merge point.
>
> Horrid hack.
> For some reason we cannot carry a flag about. So reverse the bits of the
> next pointer. Almost always you will be able to detect a bit-reversed
> pointer. You keep the start of list one and go through for a second time,
> undoing your bit mangling. Needless to say, the horrid hack is dangerous.
>
I think  there may also be a system specific solution depending on where in
the memory map
the dynamically allocated storage is.

```
 0
Reply ravishankar.s (52) 1/22/2008 11:44:25 AM

```<junky_fellow@yahoo.co.in> wrote in message
On Jan 22, 4:08 pm, santosh <santosh....@gmail.com> wrote:
> junky_fel...@yahoo.co.in wrote:

>> In addition, padding bytes need not retain their values after a write.
>> In fact, I think an attempt to write to them at all invokes undefined
>> behaviour
>
>Santosh, Can you please tell me why the padding bytes need not retain
>their values after a write ? Also, you wrote that writing to padding
>bytes may invoke undefined behaviour. Why is it so ? I could not think
>of any reason for that. Can you please tell me the reason behind it.
>
He' s wrong on the reading / writing

memset(x, 0, sizeof(x));

is correct whether x contains padding bytes or not.
as is

memcpy(&y, &x, sizeof(x));

However padding bytes are designed not to be used by the program. So the
compiler could notionally use them for a checksum or something. I doubt that
any compilers actually do this.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

```
 0
Reply regniztar (3128) 1/22/2008 11:44:43 AM

```On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
"junky_fellow@yahoo.co.in" <junky_fellow@yahoo.co.in> wrote:

>Hi,
>
>   Is there any efficient way of finding the intesection point of two
>I mean to say that, there are two singly linked lists and they meet at
>some point. I want to find out the addres of the node where the two
>
>thanks for any help...

Here is a simple approach.  Let A and B be the two lists, and let
count(A) and count(B) be the number of nodes in each list.
Suppose that count(A) >= count(B).  Skip count(A)-count(B)
elements of list A to get A'.  Now A' and B have the same lengths
so you can compare them element by element until you find the
merge point.  This is an O(length of lists) method.

There may be an O(length of distances to merge point) algorithm
but it doesn't occur to me off hand.

Why is this in comp.lang.c?

```
 0
Reply cri (1432) 1/22/2008 11:45:16 AM

```On Jan 22, 4:45=A0pm, c...@tiac.net (Richard Harter) wrote:
> On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
>
> "junky_fel...@yahoo.co.in" <junky_fel...@yahoo.co.in> wrote:
> >Hi,
>
> > =A0 Is there any efficient way of finding the intesection point of two
> >I mean to say that, there are two singly linked lists and they meet at
> >some point. I want to find out the addres of the node where the two
>
> >thanks for any help...
>
> Here is a simple approach. =A0Let A and B be the two lists, and let
> count(A) and count(B) be the number of nodes in each list.
> Suppose that count(A) >=3D count(B). =A0Skip count(A)-count(B)
> elements of list A to get A'. =A0Now A' and B have the same lengths
> so you can compare them element by element until you find the
> merge point. =A0This is an O(length of lists) method.
>
> There may be an O(length of distances to merge point) algorithm
> but it doesn't occur to me off hand.
>
> Why is this in comp.lang.c?

great. thanks for the solution.
```
 0
Reply junky_fellow (377) 1/22/2008 11:48:51 AM

```"Malcolm McLean" <regniztar@btinternet.com> writes:

> <junky_fellow@yahoo.co.in> wrote in message
>>   Is there any efficient way of finding the intesection point of two
<snip>
> struct node
> {
>   struct node *next;
>   void *data;
>    int flag;
> }
>
> Iterate from start one to then end setting all the flags.
> Iterate from start two. When you find a set flag, that's your merge point.
>
> Horrid hack.
> For some reason we cannot carry a flag about. So reverse the bits of
> the next pointer. Almost always you will be able to detect a
> bit-reversed pointer.

The traditional way to find an extra flag bit was always just to use
one of the bits in the pointer.  The most usual being the least
significant bit since this will often be 0 for link node pointers
(even on word-addressed machines).  You can also easily traverse the
list even when the bit is "in use" be one mask operation.

--
Ben.
```
 0
Reply ben.usenet (6790) 1/22/2008 12:01:39 PM

```On Jan 22, 5:01=A0pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> "Malcolm McLean" <regniz...@btinternet.com> writes:
> > <junky_fel...@yahoo.co.in> wrote in message
> >> =A0 Is there any efficient way of finding the intesection point of two
> >> singly linked lists ?
> <snip>
> > struct node
> > {
> > =A0 struct node *next;
> > =A0 void *data;
> > =A0 =A0int flag;
> > }
>
> > Iterate from start one to then end setting all the flags.
> > Iterate from start two. When you find a set flag, that's your merge poin=
t.
>
> > Horrid hack.
> > For some reason we cannot carry a flag about. So reverse the bits of
> > the next pointer. Almost always you will be able to detect a
> > bit-reversed pointer.
>
> The traditional way to find an extra flag bit was always just to use
> one of the bits in the pointer. =A0The most usual being the least
> significant bit since this will often be 0 for link node pointers
> (even on word-addressed machines). =A0You can also easily traverse the
> list even when the bit is "in use" be one mask operation.
>

Why do you say that the lsb of the structure pointer will often be 0 ?
For instance, consider a structure that has three char members.
struct test {
char c1;
char c2;
char c3;
};

Can't a compiler allocate an odd address for this structure. I am
using gcc over cygwin. I declared an array of 10 such structures and
printed the address of each of them. I found that some of the
```
 0
Reply junky_fellow (377) 1/22/2008 12:14:54 PM

```"Richard Harter" <cri@tiac.net> wrote in message
> Here is a simple approach.  Let A and B be the two lists, and let
> count(A) and count(B) be the number of nodes in each list.
> Suppose that count(A) >= count(B).  Skip count(A)-count(B)
> elements of list A to get A'.  Now A' and B have the same lengths
> so you can compare them element by element until you find the
> merge point.  This is an O(length of lists) method.
>

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

```
 0
Reply regniztar (3128) 1/22/2008 12:27:02 PM

```On Tue, 22 Jan 2008 11:45:16 GMT, cri@tiac.net (Richard Harter)
wrote:

>On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
>"junky_fellow@yahoo.co.in" <junky_fellow@yahoo.co.in> wrote:
>
>>Hi,
>>
>>   Is there any efficient way of finding the intesection point of two
>>I mean to say that, there are two singly linked lists and they meet at
>>some point. I want to find out the addres of the node where the two
>>
>>thanks for any help...
>
>Here is a simple approach.  Let A and B be the two lists, and let
>count(A) and count(B) be the number of nodes in each list.
>Suppose that count(A) >= count(B).  Skip count(A)-count(B)
>elements of list A to get A'.  Now A' and B have the same lengths
>so you can compare them element by element until you find the
>merge point.  This is an O(length of lists) method.
>
>There may be an O(length of distances to merge point) algorithm
>but it doesn't occur to me off hand.

And here is a method that doesn't depend on knowing the list
lengths.  As before, let A and B be the list lengths.  Traverse A
by one step.  Traverse B by three steps, checking to see if it
there is a match with the last element read from A.  Traverse A
by five more steps, checking for a match with the last element
read from B.  Continue, alternating lists and increasing the
steps by two each time.  When a match is found this way we know
the difference of distances to the merge point, m.  This gives us
an O(m^2 +D) method where D is the common distance to the merge
point.  This result can probably be improved.

The second method is a trifle more complicated but doesn't
require traversing the entire lists.

```
 0
Reply cri (1432) 1/22/2008 1:48:46 PM

```"junky_fellow@yahoo.co.in" <junky_fellow@yahoo.co.in> writes:

> On Jan 22, 5:01 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
<snip>
>> The traditional way to find an extra flag bit was always just to use
>> one of the bits in the pointer.  The most usual being the least
>> significant bit since this will often be 0 for link node pointers
>> (even on word-addressed machines).  You can also easily traverse the
>> list even when the bit is "in use" be one mask operation.
>
> Why do you say that the lsb of the structure pointer will often be 0 ?
> For instance, consider a structure that has three char members.
> struct test {
>         char c1;
>         char c2;
>         char c3;
> };
>
> Can't a compiler allocate an odd address for this structure.

Yes, but I was talking about linked list node pointers.  These will
have at least one pointer in them and, if that is not enough, will
usually be allocated with malloc.

Note "usually".  We are in system-specific territory here.  You can
probably break this by, for example, having a list node struct with an
odd size and making a packed array of these (using something like
will not all have a 0 LSB.

--
Ben.
```
 0
Reply ben.usenet (6790) 1/22/2008 2:00:19 PM

```On Jan 22, 1:42=A0am, Richard Heathfield <r...@see.sig.invalid> wrote:
> Ravishankar S said:
>
> <snip>
>
>
>
>
>
> > you mean point of merge of linked list ? i cannot imaging "intersection"=

>
> > p =A0=3D listA;
> > q =3D =A0listB;
>
> > while(p && q) {
> > =A0 =A0 if(p->next =3D=3D q->next) break;
> > =A0 =A0 p =3D p->next;
> > =A0 =A0 q =3D q->next;
> > }
>
> > if(p && q && (p->next =3D=3D q->next))
> > {
> > =A0 =A0 printf("Merging point found\n");
> > }
>
> > But careful: I have not tested the code !
>
> Indeed. Consider these linked lists:
>
> listA: A -- B -- C -- D
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0\
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 E -- F -- G
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0/
> listB: =A0 =A0 =A0 =A0 =A0 H -- I
>
> You compare A with H, B with I, C with E, D with F, E with G. Now the loop=

> stops, and q is NULL. You missed the merge point completely.
>
> I believe this has to be done in two nested loops (or at least, "as if" it=

> were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd=

> be delighted to be proved wrong.

Consider:
listA: A -- B -- C -- D             J -- K
\           /
E -- F -- G
/           \
listB:           H -- I             |
\            L
N -- M -- /

Or even:
listA:           C -- D             J -- K
\           /
E -- F -- G
/           \
listB:           H -- I             L

Graph problems have a nasty habit of turning out harder than they
appear at first glance.

If they can itersect, then they can probably also diverge and cycle.
If you don't test for it, funny things can happen, but not "ha-ha"
funny.
```
 0
Reply dcorbit (2698) 1/22/2008 9:47:12 PM

```user923005 <dcorbit@connx.com> writes:

> Consider:
>  listA: A -- B -- C -- D             J -- K
>                         \           /
>                          E -- F -- G
>                         /           \
>  listB:           H -- I             |
>                         \            L
>                           N -- M -- /

I don't see how this can happen in a linked list structure.  A
linked list node can have only one successor, but your nodes I
and G appear to each have two (E and N, and J and L,
respectively).
--
"...what folly I commit, I dedicate to you."
--William Shakespeare, _Troilus and Cressida_
```
 0
Reply blp (3955) 1/22/2008 10:40:10 PM

```Richard Heathfield wrote:
>
.... snip ...
>
> Indeed. Consider these linked lists:
>
> listA: A -- B -- C -- D
>                        \
>                         E -- F -- G
>                        /
> listB:           H -- I
>
> You compare A with H, B with I, C with E, D with F, E with G.
> Now the loop stops, and q is NULL. You missed the merge point
> completely.
>
> I believe this has to be done in two nested loops (or at least,
> "as if" it were two nested loops! - i.e. O(listAnodecount *
> listBnodecount)), but I'd be delighted to be proved wrong.

You can scan through the lists.  Do so, retaining L as the length
of listA, and L1 as the length of listB.  Now reverse listA in
place, and remeasure the length of list B, getting L2.

In the example, L is 7, L1 is 5, L2 is 7.  I think you can now find
the location of item E in either list.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

```
 0
Reply cbfalconer (19194) 1/22/2008 10:41:53 PM

```user923005 wrote:
>
.... snip ...
>
> Consider:
>  listA: A -- B -- C -- D             J -- K
>                         \           /
>                          E -- F -- G
>                         /           \
>  listB:           H -- I             |
>                         \            L
>                           N -- M -- /
>
> Or even:
>  listA:           C -- D             J -- K
>                         \           /
>                          E -- F -- G
>                         /           \
>  listB:           H -- I             L
>
> Graph problems have a nasty habit of turning out harder than they
> appear at first glance.
>
> If they can itersect, then they can probably also diverge and cycle.
> If you don't test for it, funny things can happen, but not "ha-ha"
> funny.

Those can't happen.  He originally specified singly linked lists.
You have to be able to form and manipulate them from:

struct node {
struct data *datum;
struct node *next;
}

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

```
 0
Reply cbfalconer (19194) 1/22/2008 11:19:28 PM

```On 22 Jan, 09:42, Richard Heathfield <r...@see.sig.invalid> wrote:
> Ravishankar S said:
>
> <snip>
>
>
>
>
>
> > you mean point of merge of linked list ? i cannot imaging "intersection"=

>
> > p =A0=3D listA;
> > q =3D =A0listB;
>
> > while(p && q) {
> > =A0 =A0 if(p->next =3D=3D q->next) break;
> > =A0 =A0 p =3D p->next;
> > =A0 =A0 q =3D q->next;
> > }
>
> > if(p && q && (p->next =3D=3D q->next))
> > {
> > =A0 =A0 printf("Merging point found\n");
> > }
>
> > But careful: I have not tested the code !
>
> Indeed. Consider these linked lists:
>
> listA: A -- B -- C -- D
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0\
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 E -- F -- G
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0/
> listB: =A0 =A0 =A0 =A0 =A0 H -- I
>
> You compare A with H, B with I, C with E, D with F, E with G. Now the loop=

> stops, and q is NULL. You missed the merge point completely.
>
> I believe this has to be done in two nested loops (or at least, "as if" it=

> were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd=

> be delighted to be proved wrong.

How about - you measure the length of the lists, subtract one from the
other, and step that number of steps into the longer list. Now step
through each list simultaneously, looking for a match.

Paul.
```
 0
Reply gw7rib (471) 1/22/2008 11:24:29 PM

```gw7...@aol.com wrote:
> Richard Heathfield <r...@see.sig.invalid> wrote:
> > ... Consider these linked lists:
>
> > listA: A -- B -- C -- D
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0\
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 E -- F -- G
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0/
> > listB: =A0 =A0 =A0 =A0 =A0 H -- I
<snip>
> > I believe this has to be done in two nested loops (or at
> > least, "as if" it were two nested loops! - i.e.
> > O(listAnodecount * listBnodecount)), but I'd
> > be delighted to be proved wrong.
>
> How about - you measure the length of the lists, subtract
> one from the other, and step that number of steps into the
> longer list. Now step through each list simultaneously,
> looking for a match.

More formally...

Declare the following variables

LA  :=3D length of list A
LB  :=3D length of list B
LB' :=3D length of list B if list A is reversed

DA  :=3D number of leading nodes distinct to A
DB  :=3D number of leading nodes distinct to B
CAB :=3D number of nodes common to A and B

=46rom observation, we have...

LA  =3D DA + CAB
LB  =3D DB + CAB
LB' =3D DB + DA + 1

Rewritten as...

DA       + CAB =3D LA
DB  + CAB =3D LB
DA + DB        =3D LB' - 1

Which is solved by...

CAB :=3D (LB - LB' + LA + 1)/2
DA  :=3D LA - CAB
DB  :=3D LB - CAB

The algorithm (including restoration of A from G) is left
as an exercise, but it should be clear that since reverse
and length count are O(N), and we perform a fixed number
of steps of each, the algorithm is O(N + M).

Or I may have forgotten to carry 1 and I'm talking bollocks. ;)

--
Peter
```
 0
Reply airia (1802) 1/23/2008 12:26:04 AM

```On Jan 22, 2:40=A0pm, Ben Pfaff <b...@cs.stanford.edu> wrote:
> user923005 <dcor...@connx.com> writes:
> > Consider:
> > =A0listA: A -- B -- C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 /
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =A0 \
> > =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 |
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 =
=A0L
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 N -- M -- /
>
> I don't see how this can happen in a linked list structure. =A0A
> linked list node can have only one successor, but your nodes I
> and G appear to each have two (E and N, and J and L,
> respectively).
listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
They share I,E,F,G
```
 0
Reply dcorbit (2698) 1/23/2008 12:30:19 AM

```On Jan 22, 9:42=A0am, Richard Heathfield <r...@see.sig.invalid> wrote:
> Indeed. Consider these linked lists:
>
> listA: A -- B -- C -- D
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0\
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 E -- F -- G
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0/
> listB: =A0 =A0 =A0 =A0 =A0 H -- I
>
> You compare A with H, B with I, C with E, D with F, E with G. Now the loop=

> stops, and q is NULL. You missed the merge point completely.
>
> I believe this has to be done in two nested loops (or at least, "as if" it=

> were two nested loops! - i.e. O(listAnodecount * listBnodecount)), but I'd=

> be delighted to be proved wrong.

You can do it easily with three loops, not nested. First follow the
linked list from A to the end, finding that the first linked list has
seven elements and ends at G. Then follow the second linked list to
find it has five elements and also ends in G. Since both lists end
with G, they must merge at some point (if they end with different
notes, they definitely don't merge). Since the first list has two
elements more, skip two elements, then go through the lists starting
at C and H and iterate until they meet.
```
 0
Reply christian.bau1 (424) 1/23/2008 12:54:46 AM

```user923005 <dcor...@connx.com> wrote:
> Ben Pfaff <b...@cs.stanford.edu> wrote:
> > user923005 <dcor...@connx.com> writes:
> > > Consider:
> > > =A0listA: A -- B -- C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
> > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 =
/
> > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
> > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =A0 =
\
> > > =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 |
> > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 =
=A0L
> > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 N -- M -- /
> >
> > I don't see how this can happen in a linked list structure.
> >=A0A linked list node can have only one successor, but your
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > nodes I and G appear to each have two (E and N, and J and
> > L, respectively).
>
> listA has nodes A,B,C,D,E,F,G,L,N,M,I
> listB has nodes H,I,E,F,G,J,K
> They share I,E,F,G

How is G's next link to both L _and_ J?

--
Peter
```
 0
Reply airia (1802) 1/23/2008 1:00:11 AM

```user923005 wrote:
> On Jan 22, 2:40 pm, Ben Pfaff <b...@cs.stanford.edu> wrote:
>> user923005 <dcor...@connx.com> writes:
>>> Consider:
>>>  listA: A -- B -- C -- D             J -- K
>>>                         \           /
>>>                          E -- F -- G
>>>                         /           \
>>>  listB:           H -- I             |
>>>                         \            L
>>>                           N -- M -- /
>> I don't see how this can happen in a linked list structure.  A
>> linked list node can have only one successor, but your nodes I
>> and G appear to each have two (E and N, and J and L,
>> respectively).
> listA has nodes A,B,C,D,E,F,G,L,N,M,I
> listB has nodes H,I,E,F,G,J,K
> They share I,E,F,G

Where does I's next pointer point? In ListA, it points nowhere, in
ListB, it points to E.
Where does G's next-pointer point? In ListA, it's L, in listB it's J.

As far as I can see, this can work as a linked list, bu only if the
central loop constitutes a circularly-linked (and therefore infinite)
list, and the three outside portions all link inward, toward the
circular loop. There's two solutions, depending upon whether the central
loop is linked in the clockwise or counter-clockwise direction.
```
 0
Reply jameskuyper (5639) 1/23/2008 3:54:59 AM

```On Wed, 23 Jan 2008 03:54:59 GMT, James Kuyper
<jameskuyper@verizon.net> wrote:

>user923005 wrote:
>> On Jan 22, 2:40 pm, Ben Pfaff <b...@cs.stanford.edu> wrote:
>>> user923005 <dcor...@connx.com> writes:
>>>> Consider:
>>>>  listA: A -- B -- C -- D             J -- K
>>>>                         \           /
>>>>                          E -- F -- G
>>>>                         /           \
>>>>  listB:           H -- I             |
>>>>                         \            L
>>>>                           N -- M -- /
>>> I don't see how this can happen in a linked list structure.  A
>>> linked list node can have only one successor, but your nodes I
>>> and G appear to each have two (E and N, and J and L,
>>> respectively).
>> listA has nodes A,B,C,D,E,F,G,L,N,M,I
>> listB has nodes H,I,E,F,G,J,K
>> They share I,E,F,G
>
>Where does I's next pointer point? In ListA, it points nowhere, in
>ListB, it points to E.
>Where does G's next-pointer point? In ListA, it's L, in listB it's J.
>
>As far as I can see, this can work as a linked list, bu only if the
>central loop constitutes a circularly-linked (and therefore infinite)
>list, and the three outside portions all link inward, toward the
>circular loop. There's two solutions, depending upon whether the central
>loop is linked in the clockwise or counter-clockwise direction.

Note that if the lists terminate in a cycle there are some issues
with the simple "determine the lengths of the lists" algorithm,
e.g., you can't simply traverse the lists to their ends.  The
second algorithm I posted works okay though.

```
 0
Reply cri (1432) 1/23/2008 4:45:12 AM

```On Jan 22, 5:00=A0pm, Peter Nilsson <ai...@acay.com.au> wrote:
> user923005 <dcor...@connx.com> wrote:
> > Ben Pfaff <b...@cs.stanford.edu> wrote:
> > > user923005 <dcor...@connx.com> writes:
> > > > Consider:
> > > > =A0listA: A -- B -- C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =
=A0 /
> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =
=A0 \
> > > > =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 |
> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =
=A0 =A0L
> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 N -- M -- /
>
> > > I don't see how this can happen in a linked list structure.
> > >=A0A linked list node can have only one successor, but your
>
> =A0 =A0 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> > > nodes I and G appear to each have two (E and N, and J and
> > > L, respectively).
>
> > listA has nodes A,B,C,D,E,F,G,L,N,M,I
> > listB has nodes H,I,E,F,G,J,K
> > They share I,E,F,G
>
> How is G's next link to both L _and_ J?
listA has nodes A,B,C,D,E,F,G,L,N,M,I

listB has nodes H,I,E,F,G,J,K

The picture above is the actual node structure, showing what is held
in common, if the graphs were actually merged.
I was trying to point out that if we are given listA and listB as
above, then the simple "find the node where they meet" strategy is not
going ot produce expected results.  If you have some sort of merge
operation, all sorts of strange things might occur.
```
 0
Reply dcorbit (2698) 1/23/2008 6:13:55 AM

```On Jan 22, 3:19=A0pm, CBFalconer <cbfalco...@yahoo.com> wrote:
> user923005 wrote:
>
> ... snip ...
>
> > Consider:
> > =A0listA: A -- B -- C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 /
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =A0 \
> > =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 |
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 =
=A0L
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 N -- M -- /
>
> > Or even:
> > =A0listA: =A0 =A0 =A0 =A0 =A0 C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 /
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =A0 \
> > =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 L
>
> > Graph problems have a nasty habit of turning out harder than they
> > appear at first glance.
>
> > If they can itersect, then they can probably also diverge and cycle.
> > If you don't test for it, funny things can happen, but not "ha-ha"
> > funny.
>
> Those can't happen. =A0He originally specified singly linked lists.
> You have to be able to form and manipulate them from:
>
> =A0 =A0 struct node {
> =A0 =A0 =A0 =A0struct data *datum;
> =A0 =A0 =A0 =A0struct node *next;
> =A0 =A0 }
>

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
If the lists could be merged, the "afterwards picture" showing the
common parts of the graph would look like my picture.

I was showing that if (after we find the first common node) all the
rest of the nodes are not identical from that point forward, then the
simple y sort of structure is not going to correctly model the data.
```
 0
Reply dcorbit (2698) 1/23/2008 6:16:39 AM

```On Jan 22, 7:54=A0pm, James Kuyper <jameskuy...@verizon.net> wrote:
> user923005 wrote:
> > On Jan 22, 2:40 pm, Ben Pfaff <b...@cs.stanford.edu> wrote:
> >> user923005 <dcor...@connx.com> writes:
> >>> Consider:
> >>> =A0listA: A -- B -- C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
> >>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 =
/
> >>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
> >>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =A0 =
\
> >>> =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 |
> >>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 =
=A0L
> >>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 N -- M -- /
> >> I don't see how this can happen in a linked list structure. =A0A
> >> linked list node can have only one successor, but your nodes I
> >> and G appear to each have two (E and N, and J and L,
> >> respectively).
> > listA has nodes A,B,C,D,E,F,G,L,N,M,I
> > listB has nodes H,I,E,F,G,J,K
> > They share I,E,F,G
>
> Where does I's next pointer point? In ListA, it points nowhere, in
> ListB, it points to E.

It would depend on how you merged them, because the matching sequences
in the list are not identical from the first match all the way to the
end of the list.

> Where does G's next-pointer point? In ListA, it's L, in listB it's J.

It would depend on how you merged them.

> As far as I can see, this can work as a linked list, bu only if the
> central loop constitutes a circularly-linked (and therefore infinite)
> list, and the three outside portions all link inward, toward the
> circular loop. There's two solutions, depending upon whether the central
> loop is linked in the clockwise or counter-clockwise direction.

The purpose of the diagram was to show that the physical data my not
form the simple Y model for the combined list.
```
 0
Reply dcorbit (2698) 1/23/2008 6:18:42 AM

```On Tue, 22 Jan 2008 22:16:39 -0800 (PST), user923005
<dcorbit@connx.com> wrote:

>On Jan 22, 3:19=A0pm, CBFalconer <cbfalco...@yahoo.com> wrote:
>> user923005 wrote:
>>
>> ... snip ...
>>
>> > Consider:
>> > =A0listA: A -- B -- C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
>> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 /
>> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
>> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =A0 \
>> > =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 |
>> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 =
>=A0L
>> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 N -- M -- /
>>
>> > Or even:
>> > =A0listA: =A0 =A0 =A0 =A0 =A0 C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
>> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 /
>> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
>> > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =A0 \
>> > =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 L
>>
>> > Graph problems have a nasty habit of turning out harder than they
>> > appear at first glance.
>>
>> > If they can itersect, then they can probably also diverge and cycle.
>> > If you don't test for it, funny things can happen, but not "ha-ha"
>> > funny.
>>
>> Those can't happen. =A0He originally specified singly linked lists.
>> You have to be able to form and manipulate them from:
>>
>> =A0 =A0 struct node {
>> =A0 =A0 =A0 =A0struct data *datum;
>> =A0 =A0 =A0 =A0struct node *next;
>> =A0 =A0 }
>>
>
>listA has nodes A,B,C,D,E,F,G,L,N,M,I
>listB has nodes H,I,E,F,G,J,K
>If the lists could be merged, the "afterwards picture" showing the
>common parts of the graph would look like my picture.
>
>I was showing that if (after we find the first common node) all the
>rest of the nodes are not identical from that point forward, then the
>simple y sort of structure is not going to correctly model the data.

The problem seems to be that what you mean by a node is different
from what every one else means by a node.  If I apprehend
correctly everyone else is including the link pointer in the
node, e.g, G can point to only one thing, whereas you are
thinking in terms of the nodes being data separate from the
linkage.  (That wording is a mess but I hope you can follow it.)

```
 0
Reply cri (1432) 1/23/2008 6:42:47 AM

```user923005 wrote, On 23/01/08 06:13:
> On Jan 22, 5:00 pm, Peter Nilsson <ai...@acay.com.au> wrote:
>> user923005 <dcor...@connx.com> wrote:
>>> Ben Pfaff <b...@cs.stanford.edu> wrote:
>>>> user923005 <dcor...@connx.com> writes:
>>>>> Consider:
>>>>>  listA: A -- B -- C -- D             J -- K
>>>>>                         \           /
>>>>>                          E -- F -- G
>>>>>                         /           \
>>>>>  listB:           H -- I             |
>>>>>                         \            L
>>>>>                           N -- M -- /
>>>> I don't see how this can happen in a linked list structure.
>>>>  A linked list node can have only one successor, but your
>>     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>
>>>> nodes I and G appear to each have two (E and N, and J and
>>>> L, respectively).
>>> listA has nodes A,B,C,D,E,F,G,L,N,M,I
>>> listB has nodes H,I,E,F,G,J,K
>>> They share I,E,F,G
>> How is G's next link to both L _and_ J?
> listA has nodes A,B,C,D,E,F,G,L,N,M,I
> G's next link is L.
>
> listB has nodes H,I,E,F,G,J,K
> G's next link is J.

So how do you get J->next to hold two different values at the same time?
That, I believe, is the point that is being raised. Remember that the
node type will be something like
struck node {
struct node *next;
struct data data;
};

> The picture above is the actual node structure, showing what is held
> in common, if the graphs were actually merged.
> I was trying to point out that if we are given listA and listB as
> above, then the simple "find the node where they meet" strategy is not
> going ot produce expected results.  If you have some sort of merge
> operation, all sorts of strange things might occur.

Ah, I think I see the difference of opinion. You are saying if the data
is the same in two different node objects then when merging the lists
you would replace them with a single object. Others have been thinking
that it does not matter what the data is, it only matters if it is
actually the same object appearing in both list. So perhaps you think of
the node structure as
struck node {
struct node *next;
struct data *data; /* This is now a pointer */
};

This means that yours is a harder problem than others have been trying
to solve.
--
Flash Gordon
```
 0
Reply spam331 (4048) 1/23/2008 8:32:05 AM

```user923005 wrote:
>> > > user923005 <dcor...@connx.com> writes:
>> > > > Consider:
>> > > > �listA: A -- B -- C -- D � � � � � � J -- K
>> > > > � � � � � � � � � � � � \ � � � � � /
>> > > > � � � � � � � � � � � � �E -- F -- G
>> > > > � � � � � � � � � � � � / � � � � � \
>> > > > �listB: � � � � � H -- I � � � � � � |
>> > > > � � � � � � � � � � � � \ � � � � � �L
>> > > > � � � � � � � � � � � � � N -- M -- /
>>
>> How is G's next link to both L _and_ J?
> listA has nodes A,B,C,D,E,F,G,L,N,M,I
> G's next link is L.
>
> listB has nodes H,I,E,F,G,J,K
> G's next link is J.
>
> The picture above is the actual node structure, showing what is held
> in common, if the graphs were actually merged.

I think you're suffering from a misconception regarding "lists". In a
single-linked list, each node has EXACTLY ONE successor, or a "next
element". (In a doubly-linked list, it also has EXACTLY ONE precedessor, but
that's not pertinent here).

Following your definition of list A, G's next element is L, and I has no
next element.

According to your def of B, there is an element I' whose next element is E,
and another one, G', whose next element is J.

Is it possible, under the condition that both definitions above hold, that
I == I' && G==G'
respectively?

Rhetorical question. The answer is no.

> I was trying to point out that if we are given listA and listB as
> above,

which isn't possible,

> then the simple "find the node where they meet" strategy is not
> going ot produce expected results.

....like so often when applying strategies to situations which cannot
exist ;-)

Do yourself a favor and actually try to implement your "convoluted list"
typical list element definition like this one:

struct list_node_t {
void *data; /* pointer to payload */
struct list_node_t *next;
} ;

Of course it's possible for the 'data' pointers of nodes in disjunct lists
to point to the same 'payload' memory location (a frequent occurrence in
real code), but that's besides the point.

robert
```
 0
Reply boblatest2 (238) 1/23/2008 8:33:01 AM

```On Jan 23, 12:33=A0am, Robert Latest <boblat...@yahoo.com> wrote:
> user923005 wrote:
> >> > > user923005 <dcor...@connx.com> writes:
> >> > > > Consider:
> >> > > > =A0listA: A -- B -- C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
> >> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0=
=A0 /
> >> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
> >> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0=
=A0 \
> >> > > > =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 |
> >> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0=
=A0 =A0L
> >> > > > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 N -- M -- /
>
> >> How is G's next link to both L _and_ J?
> > listA has nodes A,B,C,D,E,F,G,L,N,M,I
> > G's next link is L.
>
> > listB has nodes H,I,E,F,G,J,K
> > G's next link is J.
>
> > The picture above is the actual node structure, showing what is held
> > in common, if the graphs were actually merged.
>
> I think you're suffering from a misconception regarding "lists". In a
> single-linked list, each node has EXACTLY ONE successor, or a "next
> element". (In a doubly-linked list, it also has EXACTLY ONE precedessor, b=
ut
> that's not pertinent here).

True, but what if the data does not follow that pattern?

> Following your definition of list A, G's next element is L, and I has no
> next element.
>
> According to your def of B, there is an element I' whose next element is E=
,
> and another one, G', whose next element is J.
>
> Is it possible, under the condition that both definitions above hold, that=

> =A0 =A0 I =3D=3D I' && G=3D=3DG'
> respectively?
>
> Rhetorical question. The answer is no.

Look again: I gave the nodes of the two lists:

listA has nodes A,B,C,D,E,F,G,L,N,M,I

listB has nodes H,I,E,F,G,J,K

> > I was trying to point out that if we are given listA and listB as
> > above,
>
> which isn't possible,

Of course it is.

> > then the simple "find the node where they meet" strategy is not
> > going ot produce expected results.
>
> ...like so often when applying strategies to situations which cannot
> exist ;-)
>
> Do yourself a favor and actually try to implement your "convoluted list"

> typical list element definition like this one:
>
> struct list_node_t {
> =A0 =A0void *data; /* pointer to payload */
> =A0 =A0struct list_node_t *next;
>
> } ;
>
> Of course it's possible for the 'data' pointers of nodes in disjunct lists=

> to point to the same 'payload' memory location (a frequent occurrence in
> real code), but that's besides the point.

Believe it or not, I have written successful lists and graphs.
```
 0
Reply dcorbit (2698) 1/23/2008 10:25:14 AM

```On Jan 23, 12:32=A0am, Flash Gordon <s...@flash-gordon.me.uk> wrote:
> user923005 wrote, On 23/01/08 06:13:
>
>
>
>
>
> > On Jan 22, 5:00 pm, Peter Nilsson <ai...@acay.com.au> wrote:
> >> user923005 <dcor...@connx.com> wrote:
> >>> Ben Pfaff <b...@cs.stanford.edu> wrote:
> >>>> user923005 <dcor...@connx.com> writes:
> >>>>> Consider:
> >>>>> =A0listA: A -- B -- C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
> >>>>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =
=A0 /
> >>>>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
> >>>>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =
=A0 \
> >>>>> =A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 |
> >>>>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =
=A0 =A0L
> >>>>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 N -- M -- /
> >>>> I don't see how this can happen in a linked list structure.
> >>>> =A0A linked list node can have only one successor, but your
> >> =A0 =A0 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> >>>> nodes I and G appear to each have two (E and N, and J and
> >>>> L, respectively).
> >>> listA has nodes A,B,C,D,E,F,G,L,N,M,I
> >>> listB has nodes H,I,E,F,G,J,K
> >>> They share I,E,F,G
> >> How is G's next link to both L _and_ J?
> > listA has nodes A,B,C,D,E,F,G,L,N,M,I
> > G's next link is L.
>
> > listB has nodes H,I,E,F,G,J,K
> > G's next link is J.
>
> So how do you get J->next to hold two different values at the same time?
> That, I believe, is the point that is being raised. Remember that the
> node type will be something like
> struck node {
> =A0 =A0 struct node *next;
> =A0 =A0 struct data data;
>
> };
> > The picture above is the actual node structure, showing what is held
> > in common, if the graphs were actually merged.
> > I was trying to point out that if we are given listA and listB as
> > above, then the simple "find the node where they meet" strategy is not
> > going ot produce expected results. =A0If you have some sort of merge
> > operation, all sorts of strange things might occur.
>
> Ah, I think I see the difference of opinion. You are saying if the data
> is the same in two different node objects then when merging the lists
> you would replace them with a single object. Others have been thinking
> that it does not matter what the data is, it only matters if it is
> actually the same object appearing in both list. So perhaps you think of
> the node structure as
> struck node {
> =A0 =A0 struct node *next;
> =A0 =A0 struct data *data; /* This is now a pointer */
>
> };
>
> This means that yours is a harder problem than others have been trying
> to solve.

If we are searching for a common join point in a graph, I assume that
we are going to do something with it.

Other people have written their little diagrams like this:

A -- B -- C
\
D -- E  -- F
/
G -- H -- I

To show how the two common lists will join together.  I was pointing
out that unless D-E-F are identical in both lists and unless there are
no further nodes than F in either list, that strategy is not going to
work.

I guess that what I was saying (apparently with an incredible lack of
communication skill) is that if two list graphs can have different
nodes in them and they might share a common subsequence, it is not
unlikely that they will diverge and do other naughty things that
prevents merger or other useful graph operations.
```
 0
Reply dcorbit (2698) 1/23/2008 10:28:56 AM

```On Jan 22, 3:19 pm, "junky_fel...@yahoo.co.in"
<junky_fel...@yahoo.co.in> wrote:
> Hi,
>
>    Is there any efficient way of finding the intesection point of two
> I mean to say that, there are two singly linked lists and they meet at
> some point. I want to find out the addres of the node where the two
>
> thanks for any help...

here is an O(N) solution without tagging or memory allocating tech.
(btw, I personally prefer the tag-the-lsb-bit-of-pointer method, which
is simple and cool.)

first, apply an known algorithm to list A to figure out the last non-
repeated node of it. Note that list A is
either a common single list (tail point to NULL) or list with a cycle.
second, apply the same algorithm to list B to figure out the last non-
repeated node, which actually is the merge node of list A and list B.
we play a trick in the second step to make list A appears like a big
cycle as a whole. that is, the code of moving p to the next node
should be like this:
p = (p == last_non_repeated_node_of_list_a) ? head_node_of_list_a : p-
>next;

description of the 'known algorithm' (find out the merge node in a
single list with a cycle):
1) let two pointer p1 and p2 point to the head node of the single
list.
2) move forward p1 one node, p2 two nodes. repeat this step until p1
== p2.
3) keep p1 still, and p2 point back to the head node of the single
list.
then move forward p1 and p2 one node each, until they meet.
the node they meet is the merge node of the single list.
```
 0
Reply guanjunz (2) 1/23/2008 10:36:19 AM

```user923005 wrote:

> On Jan 23, 12:33 am, Robert Latest <boblat...@yahoo.com> wrote:
>> user923005 wrote:
>> >> > > user923005 <dcor...@connx.com> writes:
>> >> > > > Consider:
>> >> > > >  listA: A -- B -- C -- D             J -- K
>> >> > > >                         \           /
>> >> > > >                          E -- F -- G
>> >> > > >                         /           \
>> >> > > >  listB:           H -- I             |
>> >> > > >                         \            L
>> >> > > >                           N -- M -- /
>>
>> >> How is G's next link to both L _and_ J?
>> > listA has nodes A,B,C,D,E,F,G,L,N,M,I
>> > G's next link is L.
>>
>> > listB has nodes H,I,E,F,G,J,K
>> > G's next link is J.
>>
>> > The picture above is the actual node structure, showing what is held
>> > in common, if the graphs were actually merged.
>>
>> I think you're suffering from a misconception regarding "lists". In a
>> single-linked list, each node has EXACTLY ONE successor, or a "next
>> element". (In a doubly-linked list, it also has EXACTLY ONE precedessor, but
>> that's not pertinent here).
>
> True, but what if the data does not follow that pattern?
Then it isn't a linked list.
--
Army1987 (Replace "NOSPAM" with "email")
```
 0
Reply army1987 (668) 1/23/2008 12:11:02 PM

```user923005 a �crit :
> On Jan 22, 5:00 pm, Peter Nilsson <ai...@acay.com.au> wrote:
>> user923005 <dcor...@connx.com> wrote:
>>> Ben Pfaff <b...@cs.stanford.edu> wrote:
>>>> user923005 <dcor...@connx.com> writes:
>>>>> Consider:
>>>>>  listA: A -- B -- C -- D             J -- K
>>>>>                         \           /
>>>>>                          E -- F -- G
>>>>>                         /           \
>>>>>  listB:           H -- I             |
>>>>>                         \            L
>>>>>                           N -- M -- /
>>>> I don't see how this can happen in a linked list structure.
>>>>  A linked list node can have only one successor, but your
>>     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>
>>>> nodes I and G appear to each have two (E and N, and J and
>>>> L, respectively).
>>> listA has nodes A,B,C,D,E,F,G,L,N,M,I
>>> listB has nodes H,I,E,F,G,J,K
>>> They share I,E,F,G
>> How is G's next link to both L _and_ J?
> listA has nodes A,B,C,D,E,F,G,L,N,M,I
> G's next link is L.
>
> listB has nodes H,I,E,F,G,J,K
> G's next link is J.
>
> The picture above is the actual node structure, showing what is held
> in common, if the graphs were actually merged.
> I was trying to point out that if we are given listA and listB as
> above, then the simple "find the node where they meet" strategy is not
> going ot produce expected results.  If you have some sort of merge
> operation, all sorts of strange things might occur.

Consider the following program:

/********************************/
#include <stdio.h>
#include <stdlib.h>

struct node
{
struct node* next;
char data;
};

/* Node instances */
static struct node a = {NULL, 'A'};
static struct node b = {NULL, 'B'};
static struct node c = {NULL, 'C'};
static struct node d = {NULL, 'D'};
static struct node e = {NULL, 'E'};
static struct node f = {NULL, 'F'};
static struct node g = {NULL, 'G'};
static struct node h = {NULL, 'H'};
static struct node i = {NULL, 'I'};
static struct node j = {NULL, 'J'};
static struct node k = {NULL, 'K'};
static struct node l = {NULL, 'L'};
static struct node m = {NULL, 'M'};
static struct node n = {NULL, 'N'};

/* listA has nodes A,B,C,D,E,F,G,L,N,M,I */
struct node* makeListA(void)
{
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
f.next = &g;
g.next = &l; /* g.next points to l */
l.next = &n;
n.next = &m;
m.next = &i;
i.next = NULL;
return(&a);
}

/* listB has nodes H,I,E,F,G,J,K */
struct node* makeListB(void)
{
h.next = &i;
i.next = &e;
e.next = &f;
f.next = &g;
g.next = &j; /* g.next points to j */
j.next = &k;
k.next = NULL;
return(&h);
}

/* Print all elements of the list (avoid circular lists!) */
void printList(struct node* list)
{
struct node* iter = NULL;
for(iter = list ; iter != NULL ; iter = iter->next)
{
printf("%c ", iter->data);
}
printf("\n");
}

int main(int argc, char* argv[])
{
/* Make listA first, then listB */
{
struct node* listA = makeListA();
struct node* listB = makeListB();
printf("listA: "); printList(listA);
printf("listB: "); printList(listB);
}

printf("\n");

/* Make listB first, then listA */
{
struct node* listB = makeListB();
struct node* listA = makeListA();
printf("listA: "); printList(listA);
printf("listB: "); printList(listB);
}

exit(EXIT_SUCCESS);
}
/********************************/

The output is:
listA: A B C D E F G J K
listB: H I E F G J K

listA: A B C D E F G L N M I
listB: H I

I think you can see here what is confusing people: if you want to consider listA
and listB being defined as you said (respectively A,B,C,D,E,F,G,L,N,M,I and
H,I,E,F,G,J,K), this cannot be done using linked-list structures.

Maybe you were considering that node G can be instanciated two times, let's say
as being declared like
struct node g1 = {NULL, 'G'}, g2 = {NULL, 'G'};
I do not think this was the point of the O/P who wants to "to find out the
addres of the node where the two linked intersect", which I understand as
considering the assertion &g1==&g2, rather than g1.data==g2.data
```
 0

```user923005 wrote:
....
> Other people have written their little diagrams like this:
>
> A -- B -- C
>             \
>               D -- E  -- F
>             /
> G -- H -- I
>
> To show how the two common lists will join together.  I was pointing
> out that unless D-E-F are identical in both lists and unless there are
> no further nodes than F in either list, that strategy is not going to
> work.
>
> I guess that what I was saying (apparently with an incredible lack of
> communication skill) is that if two list graphs can have different
> nodes in them and they might share a common subsequence, it is not
> unlikely that they will diverge and do other naughty things that
> prevents merger or other useful graph operations.

Several people, including myself, have been assuming that the diagram
above was meant to describe a single set of 9 singly-linked list nodes,
where I.next points to D, and C.next also points to D. You seem to be
talking about two separate sets of 6 list nodes pointing at (or
containing?) 9 distinct pieces of data, where the fourth node of the
first set is distinct from the fourth node of the second set, but that
both nodes point at (or contain?) the same data. I have no idea which
interpretation Richard Heathfield actually intended when he drew his
diagram.
```
 0
Reply jameskuyper (5639) 1/23/2008 12:55:42 PM

```Flash Gordon <spam@flash-gordon.me.uk> wrote:

> user923005 wrote, On 23/01/08 06:13:
> > I was trying to point out that if we are given listA and listB as
> > above, then the simple "find the node where they meet" strategy is not
> > going ot produce expected results.  If you have some sort of merge
> > operation, all sorts of strange things might occur.
>
> Ah, I think I see the difference of opinion. You are saying if the data
> is the same in two different node objects then when merging the lists
> you would replace them with a single object. Others have been thinking
> that it does not matter what the data is, it only matters if it is
> actually the same object appearing in both list.

> This means that yours is a harder problem than others have been trying
> to solve.

No, what it means is that the problem _as stated_ is not quite clear
enough. It's probably clear to the person who framed it which version is
meant, but without any context, either interpretation is a valid one -
although I'd agree that the "common" interpretation is more likely the
intended one than Dann's.

Richard
```
 0
Reply rlb (4118) 1/23/2008 3:43:28 PM

```In article <5vocdtF1m9gt4U1@mid.dfncis.de>,
Robert Latest  <boblatest@yahoo.com> wrote:
>user923005 wrote:
>>> > > user923005 <dcor...@connx.com> writes:
>>> > > > Consider:
>>> > > >  listA: A -- B -- C -- D             J -- K
>>> > > >                         \           /
>>> > > >                          E -- F -- G
>>> > > >                         /           \
>>> > > >  listB:           H -- I             |
>>> > > >                         \            L
>>> > > >                           N -- M -- /
>>>
>>> How is G's next link to both L _and_ J?
>> listA has nodes A,B,C,D,E,F,G,L,N,M,I
>> G's next link is L.
>>
>> listB has nodes H,I,E,F,G,J,K
>> G's next link is J.
>>
>> The picture above is the actual node structure, showing what is held
>> in common, if the graphs were actually merged.
>
>I think you're suffering from a misconception regarding "lists".

user923005 is bright enough, and has a solid enough understanding of
the basics, that I don't think "misconception" is the right word.
I think the problem is that he's talking about equivalence of list
nodes, and everybody else is talking about identity.

If you want to have two lists with the ordering indicated by the
diagram above, you need to have two nodes containing the values I,E,F,G
(since listA needs to have G->L and listB needs G->J, and the common
predecessors need to be distinct to have links to the distinct
successors).

If your comparison is "is this the same node" (checking identity),
you'll never find a duplicate in those lists (since all of their common
values need , while you could if you have lists like:
listC:  A,B,C,D,E
listD:  F,G,C,D,E
since they have a common tail after some point, and can share the
actual nodes as well as the values (since at C and every step after
that, equivalent nodes have equivalent successors).

If your comparison is "does this node have the same value" (checking
equivalence), you'll find a match in I-E-F-G in the original example as
well as in C-D-E in the simpler example.

dave

--
Dave Vandervies                                   dj3vande at eskimo dot com
Correction: Number of *solicited* emails deleted: 29. You deleted everything
you asked for.    Here is an equivalent measure:
rm /var/spool/mail/*                --Richard Heathfield in comp.programming
```
 0
Reply dj3vande3 (264) 1/23/2008 4:01:37 PM

```On Wed, 23 Jan 2008 02:36:19 -0800 (PST), guanjun
<guanjunz@gmail.com> wrote:

>On Jan 22, 3:19 pm, "junky_fel...@yahoo.co.in"
><junky_fel...@yahoo.co.in> wrote:
>> Hi,
>>
>>    Is there any efficient way of finding the intesection point of two
>> I mean to say that, there are two singly linked lists and they meet at
>> some point. I want to find out the addres of the node where the two
>>
>> thanks for any help...
>
>here is an O(N) solution without tagging or memory allocating tech.
>(btw, I personally prefer the tag-the-lsb-bit-of-pointer method, which
>is simple and cool.)
>
>first, apply an known algorithm to list A to figure out the last non-
>repeated node of it. Note that list A is
>either a common single list (tail point to NULL) or list with a cycle.
>second, apply the same algorithm to list B to figure out the last non-
>repeated node, which actually is the merge node of list A and list B.

There is an error here.  When the two lists terminate in a cycle
each list can join the cycle at different nodes.  Each is a
legitimate merge node, i.e., we can follow A until it reaches B's
merge point or we can follow B until it reaches A's merge point.
There is no singular "the merge point".

One can argue that the phrasing of the original question
implicitly specified null terminated lists since it used the
wording "the intersection point".  Alternatively, we can remove
the ambiguity by adopting some criterion for the "best" merge
point, e.g., the one that minimizes the combined lengths to the
merge point, although this fails if the two merge points are on
exact opposite sides of the cycle.

Even if we rule out cycles, a "good" algorithm should be able to
handle them.  As it happens, the second algorithm I posted does
and will produce the "earlier" merge point.

>we play a trick in the second step to make list A appears like a big
>cycle as a whole. that is, the code of moving p to the next node
>should be like this:
>p = (p == last_non_repeated_node_of_list_a) ? head_node_of_list_a : p-
>>next;
>
>description of the 'known algorithm' (find out the merge node in a
>single list with a cycle):
>1) let two pointer p1 and p2 point to the head node of the single
>list.
>2) move forward p1 one node, p2 two nodes. repeat this step until p1
>== p2.
>3) keep p1 still, and p2 point back to the head node of the single
>list.
>then move forward p1 and p2 one node each, until they meet.
>the node they meet is the merge node of the single list.

```
 0
Reply cri (1432) 1/23/2008 5:58:52 PM

```Richard Bos wrote, On 23/01/08 15:43:
> Flash Gordon <spam@flash-gordon.me.uk> wrote:

<snip>

>> This means that yours is a harder problem than others have been trying
>> to solve.
>
> No, what it means is that the problem _as stated_ is not quite clear
> enough. It's probably clear to the person who framed it which version is
> meant, but without any context, either interpretation is a valid one -
> although I'd agree that the "common" interpretation is more likely the
> intended one than Dann's.

I did not say that the problem as stated was clearly enough, I said that
people were trying to solve different problems.
--
Flash Gordon
```
 0
Reply spam331 (4048) 1/23/2008 6:30:50 PM

```In article <3d4b5bc5-312e-4050-8afe-f6a1a25a0842@e4g2000hsg.googlegroups.com>,
junky_fellow@yahoo.co.in <junky_fellow@yahoo.co.in> wrote:
>   Is there any efficient way of finding the intesection point of two
>I mean to say that, there are two singly linked lists and they meet at
>some point. I want to find out the addres of the node where the two

Reverse both lists and compare the reversed lists?
```
 0
Reply ike5 (224) 1/24/2008 8:12:23 PM

```Ike Naar wrote:
> junky_fellow@yahoo.co.in <junky_fellow@yahoo.co.in> wrote:
>
>> Is there any efficient way of finding the intesection point of
>> two singly linked lists ?  I mean to say that, there are two
>> singly linked lists and they meet at some point. I want to find
>> out the addres of the node where the two linked intersect.
>
> Reverse both lists and compare the reversed lists?

Initial lists:

list1:   A --> B --> C -\
\
--> D --> E
/
list2:   X --> Y -------/

Reverse list1 and get: (remember Ys next ptr unchanged)

list1:   E -------------\
\
--> D --> C --> B --> A
/
list2:   X --> Y -------/

Now reverse list2 and get: (Es next ptr unchanged)

list1:   E --------------\
\
--> D --> Y --> X
/
list2:   A --> B --> C --/

==========================================
However, if we first reverse list2, we get:

list1:   A --> B --> C -\
\
--> D --> Y --> X
/
list2:   E -------------/

Now reverse list1 and get:

list1:   X --> Y -------\
\
--> D --> C --> B --> A
/
list2:   E -------------/

and I cannot see what is common to the two double reversals that
identifies the original node C (or Y), nor the reversal steps need
to regain the original configuration.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

```
 0
Reply cbfalconer (19194) 1/24/2008 10:47:12 PM

```dj3vande@csclub.uwaterloo.ca.invalid wrote:

> If your comparison is "does this node have the same value" (checking
> equivalence), you'll find a match in I-E-F-G in the original example as
> well as in C-D-E in the simpler example.

Yes, but if we talk about "values" (or "payloads", as I like to call them)
of lists then the OP should have said so. I'm doubtful that he gets the
difference.

robert
```
 0
Reply boblatest2 (238) 1/25/2008 9:41:18 AM

```user923005 wrote:

> Believe it or not, I have written successful lists and graphs.

I believe you when you show us a small example of crossing-over linked
lists.

robert
```
 0
Reply boblatest2 (238) 1/25/2008 9:42:50 AM

```CBFalconer  <cbfalconer@maineline.net> wrote:
>Ike Naar wrote:
>> Reverse both lists and compare the reversed lists?
>
>Initial lists:
>
>list1:   A --> B --> C -\
>                         \
>                          --> D --> E
>                         /
>list2:   X --> Y -------/
>
> [snipped: in-place place reveral list1 and list2]
>
>and I cannot see what is common to the two double reversals that
>identifies the original node C (or Y), nor the reversal steps need
>to regain the original configuration.

What I actually meant to say (and I did not make myself very clear) was:
produce a reversed _copy_ of each list, and compare the reversed copies,

list1: A B C D E     reversed copy of list1: E D C B A
list2: X Y D E       reversed copy of list2: E D Y X
common prefix of reversed copies: E D

A far more elegant solution has been posted elsethread:
Make sure both lists have equal length, by trimming the head part of
the longest list; then find the first common element of the resulting
lists.
```
 0
Reply ike5 (224) 1/25/2008 10:21:48 AM

```In article <3d4b5bc5-312e-4050-8afe-f6a1a25a0842@e4g2000hsg.googlegroups.com>,
junky_fellow@yahoo.co.in <junky_fellow@yahoo.co.in> wrote:

>   Is there any efficient way of finding the intesection point of two
>I mean to say that, there are two singly linked lists and they meet at
>some point. I want to find out the addres of the node where the two

Observe that the problem is easy if the lists are the same length:
just cdr down them in parallel until you find the common node.

So: determine the length of the lists.  Call them l and m, and suppose
l < m (that is, the first list is shorter).  Now the tail of the
second list starting after (m-l) elements is the same length as the
first list.

This is of course order N.

-- Richard
--
:wq
```
 0
Reply richard91 (3692) 1/25/2008 12:11:34 PM

```Robert Latest <boblatest@yahoo.com> writes:

> user923005 wrote:
>
>> Believe it or not, I have written successful lists and graphs.
>
> I believe you when you show us a small example of crossing-over linked
> lists.

I think that dcorbit is talking about lists in which the content is
pointed to by, rather than contain in, the nodes.  I C:

struct list_node {
struct list_node *next;
Content *content; /* void * if one wants to be generic */
};

With this structure, two lists may share data so that diagrams in
which some items are common to multiple lists are then possible.

--
Ben.
```
 0
Reply ben.usenet (6790) 1/25/2008 3:32:46 PM

```CBFalconer wrote:
>
> Richard Heathfield wrote:
> >
> ... snip ...
> >
> > Indeed. Consider these linked lists:
> >
> > listA: A -- B -- C -- D
> >                        \
> >                         E -- F -- G
> >                        /
> > listB:           H -- I

> You can scan through the lists.  Do so, retaining L as the length
> of listA, and L1 as the length of listB.  Now reverse listA in
> place, and remeasure the length of list B, getting L2.
>
> In the example, L is 7, L1 is 5, L2 is 7.  I think you can now find
> the location of item E in either list.

If the first node of listA is node number (0),
then item E is node number (((L - L1 + L2) - 1) / 2) of listA.

--
pete
```
 0
Reply pfiland (6614) 1/28/2008 12:18:44 PM

```pete wrote:
>
> CBFalconer wrote:
> >
> > Richard Heathfield wrote:
> > >
> > ... snip ...
> > >
> > > Indeed. Consider these linked lists:
> > >
> > > listA: A -- B -- C -- D
> > >                        \
> > >                         E -- F -- G
> > >                        /
> > > listB:           H -- I
>
> > You can scan through the lists.  Do so, retaining L as the length
> > of listA, and L1 as the length of listB.  Now reverse listA in
> > place, and remeasure the length of list B, getting L2.
> >
> > In the example, L is 7, L1 is 5, L2 is 7.  I think you can now find
> > the location of item E in either list.
>
> If the first node of listA is node number (0),
> then item E is node number (((L - L1 + L2) - 1) / 2) of listA.

That would be after listA has been reversed again.

--
pete
```
 0
Reply pfiland (6614) 1/28/2008 12:41:15 PM

55 Replies
54 Views

Similar Articles

12/9/2013 7:39:47 PM
[PageSpeed]