Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > linked list question

Reply
Thread Tools

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

 
Reply With Quote
 
 
 
 
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
> 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 !





 
Reply With Quote
 
 
 
 
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"
> 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
 
Reply With Quote
 
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"
> > 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
 
Reply With Quote
 
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"
> > 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
 
Reply With Quote
 
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
> 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




 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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
> > 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.
 
Reply With Quote
 
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
>> > 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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Airplane Program with Linked Lists. The linked list portion is veryconfusing to me. jawdoc C++ 9 03-10-2008 03:38 AM
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments