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

[junky_fellow]

On Jan 22, 4:08*pm, santosh <santosh....@gm ail.comwrote:

junky_fel...@ya hoo.co.in wrote:

On Jan 22, 3:19*pm, "Malcolm McLean" <regniz...@btin ternet.comwrote :

<junky_fel...@y ahoo.co.inwrote 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.

[Richard Harter]

On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
"ju**********@y ahoo.co.in" <ju**********@y ahoo.co.inwrote :

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

[Ravishankar S]

"Malcolm McLean" <re*******@btin ternet.comwrote in message
news:Mv******** *************** *******@bt.com. ..

>
<ju**********@y ahoo.co.inwrote 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.

I think there may also be a system specific solution depending on where in
the memory map
the dynamically allocated storage is.

[junky_fellow]

On Jan 22, 4:45*pm, [e-mail] (Richard Harter) wrote:

On Mon, 21 Jan 2008 23:19:46 -0800 (PST),

"junky_fel...@y ahoo.co.in" <junky_fel...@y ahoo.co.inwrote :

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?

great. thanks for the solution.

[Ben Bacarisse]

"Malcolm McLean" <re*******@btin ternet.comwrite s:

<ju**********@y ahoo.co.inwrote 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.

--
Ben.

[junky_fellow]

On Jan 22, 5:01*pm, Ben Bacarisse <ben.use...@bsb .me.ukwrote:

"Malcolm McLean" <regniz...@btin ternet.comwrite s:

<junky_fel...@y ahoo.co.inwrote 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
addresses were odd.

[Malcolm McLean]

"Richard Harter" <cr*@tiac.netwr ote 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.

That's the answer.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Richard Harter]

On Tue, 22 Jan 2008 11:45:16 GMT, cr*@tiac.net (Richard Harter)
wrote:

>On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
"ju**********@ yahoo.co.in" <ju**********@y ahoo.co.inwrote :

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

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]

"ju**********@y ahoo.co.in" <ju**********@y ahoo.co.inwrite s:

On Jan 22, 5:01Â*pm, Ben Bacarisse <ben.use...@bsb .me.ukwrote:

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

--
Ben.

[user923005]

On Jan 22, 1:42*am, Richard Heathfield <[e-mail].i nvalidwrote:

Ravishankar S said:

<snip>

you mean point of merge of linked list ? i cannot imaging "intersecti on"
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(listAnodecoun t * listBnodecount) ), but I'd
be delighted to be proved wrong.

Consider:
listA: A -- B -- C -- D J -- K
\ /
E -- F -- G
/ \
listB: H -- I |
\ L
N -- M -- /

Or even:
listA: C -- D J -- K
\ /
E -- F -- G
/ \
listB: H -- I L
Graph problems have a nasty habit of turning out harder than they
appear at first glance.

If they can itersect, then they can probably also diverge and cycle.
If you don't test for it, funny things can happen, but not "ha-ha"
funny.