linked list question
 

Hi,

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...

Re: linked list question
 

<junky_fellow@yahoo.co.in> wrote in message
news:3d4b5bc5-312e-4050-8afe-f6a1a25a0842@e4g2000hsg.googlegroups.com...
> Hi,
>
> 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...

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

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 !

Re: linked list question
 

Ravishankar S said:

<snip>

> you mean point of merge of linked list ? i cannot imaging "intersection"
> of singly linked
>
> 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.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

Re: linked list question
 

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

> Ravishankar S said:
>
> <snip>
>
> > you mean point of merge of linked list ? i cannot imaging "intersection"
> > of singly linked
> >
> > 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

Re: linked list question
 

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"
> > of singly linked
>
> > 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

Re: linked list question
 

<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
> 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.

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

Re: linked list question
 

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

Re: linked list question
 

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

Re: linked list question
 

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 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.

Re: linked list question
 

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
>> > 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.