Velocity Reviews > linked list question

junky_fellow@yahoo.co.in
Guest
Posts: n/a

 01-22-2008
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...

Ravishankar S
Guest
Posts: n/a

 01-22-2008
<(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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 !

Richard Heathfield
Guest
Posts: n/a

 01-22-2008
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

Jean-Marc Bourguet
Guest
Posts: n/a

 01-22-2008
Richard Heathfield <(E-Mail Removed)> 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

micans@gmail.com
Guest
Posts: n/a

 01-22-2008
On Jan 22, 9:42 am, Richard Heathfield <(E-Mail Removed)> 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

Malcolm McLean
Guest
Posts: n/a

 01-22-2008

<(E-Mail Removed)> 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

Robert Latest
Guest
Posts: n/a

 01-22-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) 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

micans@gmail.com
Guest
Posts: n/a

 01-22-2008
On Jan 22, 10:23 am, Robert Latest <(E-Mail Removed)> wrote:
> (E-Mail Removed) 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

junky_fellow@yahoo.co.in
Guest
Posts: n/a

 01-22-2008
On Jan 22, 3:19*pm, "Malcolm McLean" <(E-Mail Removed)> wrote:
> <(E-Mail Removed)> 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.
>

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.

santosh
Guest
Posts: n/a

 01-22-2008
(E-Mail Removed) wrote:

> On Jan 22, 3:19*pm, "Malcolm McLean" <(E-Mail Removed)> wrote:
>> <(E-Mail Removed)> 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.