linked list question

[junky_fellow]

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

 

[Ravishankar S]

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 !

 

[Richard Heathfield]

Ravishankar S said:

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.

 

[Jean-Marc Bourguet]

Ravishankar S said:



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.

 

[micans]

Ravishankar S said:

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

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]

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.

 

[Robert Latest]

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]

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

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]

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.

 

[junky_fellow]

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.

 

[Ravishankar S]

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.

 

[Malcolm McLean]

(e-mail address removed) wrote:

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.

 

[Richard Harter]

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

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?

 

[junky_fellow]

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.

 

[Ben Bacarisse]

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.

 

[junky_fellow]

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
addresses were odd.

 

[Malcolm McLean]

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.

That's the answer.

 

[Richard Harter]

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.

 

[Ben Bacarisse]

On Jan 22, 5:01 pm, Ben Bacarisse <[email protected]> wrote:

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
__attribute__((packed)) in gcc). A linked list made from this array
will not all have a 0 LSB.