Discussion in 'C Programming' started by junky_fellow@yahoo.co.in, Jan 22, 2008.

1. ### Guest

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

, Jan 22, 2008

2. ### Ravishankar SGuest

<> wrote in message
news:...
> 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 !

Ravishankar S, Jan 22, 2008

3. ### Richard HeathfieldGuest

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

Richard Heathfield, Jan 22, 2008
4. ### Jean-Marc BourguetGuest

Richard Heathfield <> 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

Jean-Marc Bourguet, Jan 22, 2008
5. ### Guest

On Jan 22, 9:42 am, Richard Heathfield <> 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

, Jan 22, 2008
6. ### Malcolm McLeanGuest

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

Malcolm McLean, Jan 22, 2008
7. ### Robert LatestGuest

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

Robert Latest, Jan 22, 2008
8. ### Guest

On Jan 22, 10:23 am, Robert Latest <> wrote:
> 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

, Jan 22, 2008
9. ### Guest

On Jan 22, 3:19 pm, "Malcolm McLean" <> wrote:
> <> 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.

, Jan 22, 2008
10. ### santoshGuest

wrote:

> On Jan 22, 3:19 pm, "Malcolm McLean" <> wrote:
>> <> 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.

santosh, Jan 22, 2008
11. ### Guest

On Jan 22, 4:08 pm, santosh <> wrote:
> wrote:
> > On Jan 22, 3:19 pm, "Malcolm McLean" <> wrote:
> >> <> 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.

, Jan 22, 2008
12. ### Ravishankar SGuest

"Malcolm McLean" <> wrote in message
news:...
>
> <> 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.

Ravishankar S, Jan 22, 2008
13. ### Malcolm McLeanGuest

<> wrote in message
On Jan 22, 4:08 pm, santosh <> wrote:
> 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

Malcolm McLean, Jan 22, 2008
14. ### Richard HarterGuest

On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
"" <> 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?

Richard Harter, Jan 22, 2008
15. ### Guest

On Jan 22, 4:45 pm, (Richard Harter) wrote:
> On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
>
> "" <> 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?

great. thanks for the solution.

, Jan 22, 2008
16. ### Ben BacarisseGuest

"Malcolm McLean" <> writes:

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

Ben Bacarisse, Jan 22, 2008
17. ### Guest

On Jan 22, 5:01 pm, Ben Bacarisse <> wrote:
> "Malcolm McLean" <> writes:
> > <> wrote in message
> >>   Is there any efficient way of finding the intesection point of two
> >> singly linked lists ?

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

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

, Jan 22, 2008
18. ### Malcolm McLeanGuest

"Richard Harter" <> 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

Malcolm McLean, Jan 22, 2008
19. ### Richard HarterGuest

On Tue, 22 Jan 2008 11:45:16 GMT, (Richard Harter)
wrote:

>On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
>"" <> 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.

Richard Harter, Jan 22, 2008
20. ### Ben BacarisseGuest

"" <> writes:

> On Jan 22, 5:01Â pm, Ben Bacarisse <> 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