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]

<ju**********@yahoo.co.inwrote in message
news:3d**********************************@e4g2000h sg.googlegroups.com...

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:

<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

[Jean-Marc Bourguet]

Richard Heathfield <rj*@see.sig.invalidwrites:

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

[micans]

On Jan 22, 9:42 am, Richard Heathfield <[e-mail]:

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

[Malcolm McLean]

<ju**********@yahoo.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.

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

[Robert Latest]

mi****@gmail.com 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]

On Jan 22, 10:23 am, Robert Latest <[e-mail]:

[e-mail] 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]

On Jan 22, 3:19*pm, "Malcolm McLean" <[e-mail]:

<[e-mail] 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.

[santosh]

ju**********@yahoo.co.in wrote:

On Jan 22, 3:19*pm, "Malcolm McLean" <[e-mail]:

><[e-mail] 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.

[junky_fellow]

On Jan 22, 4:08*pm, santosh <[e-mail]:

[e-mail] wrote:

On Jan 22, 3:19*pm, "Malcolm McLean" <[e-mail]:

<[e-mail] 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**********@yahoo.co.in" <ju**********@yahoo.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*******@btinternet.comwrote in message
news:Mv******************************@bt.com...

>
<ju**********@yahoo.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),

"[e-mail]" <[e-mail]:

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*******@btinternet.comwrites:

<ju**********@yahoo.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 <[e-mail]:

"Malcolm McLean" <[e-mail]:

<[e-mail] 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.netwrote 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**********@yahoo.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**********@yahoo.co.in" <ju**********@yahoo.co.inwrites:

On Jan 22, 5:01Â*pm, Ben Bacarisse <[e-mail]:

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

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.

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.

[Ben Pfaff]

user923005 <dc*****@connx.comwrites:

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

I don't see how this can happen in a linked list structure. A
linked list node can have only one successor, but your nodes I
and G appear to each have two (E and N, and J and L,
respectively).
--
"...what folly I commit, I dedicate to you."
--William Shakespeare, _Troilus and Cressida_

[CBFalconer]

Richard Heathfield wrote:

>

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

You can scan through the lists. Do so, retaining L as the length
of listA, and L1 as the length of listB. Now reverse listA in
place, and remeasure the length of list B, getting L2.

In the example, L is 7, L1 is 5, L2 is 7. I think you can now find
the location of item E in either list.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
--
Posted via a free Usenet account from http://www.teranews.com

[gw7rib]

On 22 Jan, 09:42, Richard Heathfield <[e-mail]:

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.

How about - you measure the length of the lists, subtract one from the
other, and step that number of steps into the longer list. Now step
through each list simultaneously, looking for a match.

Paul.

[Peter Nilsson]

[e-mail] wrote:

Richard Heathfield <[e-mail]:

... Consider these linked lists:

listA: A -- B -- C -- D
* * * * * * * * * * * *\
* * * * * * * * * * * * E -- F -- G
* * * * * * * * * * * */
listB: * * * * * H -- I

<snip>

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.

How about - you measure the length of the lists, subtract
one from the other, and step that number of steps into the
longer list. Now step through each list simultaneously,
looking for a match.

More formally...

Declare the following variables

LA := length of list A
LB := length of list B
LB' := length of list B if list A is reversed

DA := number of leading nodes distinct to A
DB := number of leading nodes distinct to B
CAB := number of nodes common to A and B

From observation, we have...

LA = DA + CAB
LB = DB + CAB
LB' = DB + DA + 1

Rewritten as...

DA + CAB = LA
DB + CAB = LB
DA + DB = LB' - 1

Which is solved by...

CAB := (LB - LB' + LA + 1)/2
DA := LA - CAB
DB := LB - CAB

The algorithm (including restoration of A from G) is left
as an exercise, but it should be clear that since reverse
and length count are O(N), and we perform a fixed number
of steps of each, the algorithm is O(N + M).

Or I may have forgotten to carry 1 and I'm talking bollocks. ;)

--
Peter

[user923005]

On Jan 22, 2:40*pm, Ben Pfaff <[e-mail]:

user923005 <[e-mail]:

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

I don't see how this can happen in a linked list structure. *A
linked list node can have only one successor, but your nodes I
and G appear to each have two (E and N, and J and L,
respectively).

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
They share I,E,F,G

[christian.bau]

On Jan 22, 9:42*am, Richard Heathfield <[e-mail]:

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 it easily with three loops, not nested. First follow the
linked list from A to the end, finding that the first linked list has
seven elements and ends at G. Then follow the second linked list to
find it has five elements and also ends in G. Since both lists end
with G, they must merge at some point (if they end with different
notes, they definitely don't merge). Since the first list has two
elements more, skip two elements, then go through the lists starting
at C and H and iterate until they meet.

[Peter Nilsson]

user923005 <[e-mail]:

Ben Pfaff <[e-mail]:

user923005 <[e-mail]:

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

I don't see how this can happen in a linked list structure.
*A linked list node can have only one successor, but your

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

nodes I and G appear to each have two (E and N, and J and
L, respectively).

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
They share I,E,F,G

How is G's next link to both L _and_ J?

--
Peter

[CBFalconer]

user923005 wrote:

>

.... snip ...

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

Those can't happen. He originally specified singly linked lists.
You have to be able to form and manipulate them from:

struct node {
struct data *datum;
struct node *next;
}

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

[user923005]

On Jan 22, 5:00*pm, Peter Nilsson <[e-mail]:

user923005 <[e-mail]:

Ben Pfaff <[e-mail]:

user923005 <[e-mail]:
Consider:
*listA: A -- B -- C -- D * * * * * * J -- K
* * * * * * * * * * * * \ * * * * * /
* * * * * * * * * * * * *E -- F -- G
* * * * * * * * * * * * / * * * * * \
*listB: * * * * * H -- I * * * * * * |
* * * * * * * * * * * * \ * * * * * *L
* * * * * * * * * * * * * N -- M -- /

I don't see how this can happen in a linked list structure.
>*A linked list node can have only one successor, but your

* * ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

nodes I and G appear to each have two (E and N, and J and
L, respectively).

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
They share I,E,F,G

How is G's next link to both L _and_ J?

listA has nodes A,B,C,D,E,F,G,L,N,M,I
G's next link is L.

listB has nodes H,I,E,F,G,J,K
G's next link is J.

The picture above is the actual node structure, showing what is held
in common, if the graphs were actually merged.
I was trying to point out that if we are given listA and listB as
above, then the simple "find the node where they meet" strategy is not
going ot produce expected results. If you have some sort of merge
operation, all sorts of strange things might occur.

[user923005]

On Jan 22, 3:19*pm, CBFalconer <[e-mail]:

user923005 wrote:

... snip ...

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.

Those can't happen. *He originally specified singly linked lists.
You have to be able to form and manipulate them from:

* * struct node {
* * * *struct data *datum;
* * * *struct node *next;
* * }

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
If the lists could be merged, the "afterwards picture" showing the
common parts of the graph would look like my picture.

I was showing that if (after we find the first common node) all the
rest of the nodes are not identical from that point forward, then the
simple y sort of structure is not going to correctly model the data.

[Richard Harter]

On Tue, 22 Jan 2008 22:16:39 -0800 (PST), user923005
<dc*****@connx.comwrote:

>On Jan 22, 3:19=A0pm, CBFalconer <[e-mail]:

>user923005 wrote:

... snip ...

Consider:
=A0listA: A -- B -- C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 /
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =A0 \
=A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 |
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 =

=A0L

=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 N -- M -- /

Or even:
=A0listA: =A0 =A0 =A0 =A0 =A0 C -- D =A0 =A0 =A0 =A0 =A0 =A0 J -- K
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 \ =A0 =A0 =A0 =A0 =A0 /
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0E -- F -- G
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 / =A0 =A0 =A0 =A0 =A0 \
=A0listB: =A0 =A0 =A0 =A0 =A0 H -- I =A0 =A0 =A0 =A0 =A0 =A0 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.

Those can't happen. =A0He originally specified singly linked lists.
You have to be able to form and manipulate them from:

=A0 =A0 struct node {
=A0 =A0 =A0 =A0struct data *datum;
=A0 =A0 =A0 =A0struct node *next;
=A0 =A0 }

listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
If the lists could be merged, the "afterwards picture" showing the
common parts of the graph would look like my picture.

I was showing that if (after we find the first common node) all the
rest of the nodes are not identical from that point forward, then the
simple y sort of structure is not going to correctly model the data.

The problem seems to be that what you mean by a node is different
from what every one else means by a node. If I apprehend
correctly everyone else is including the link pointer in the
node, e.g, G can point to only one thing, whereas you are
thinking in terms of the nodes being data separate from the
linkage. (That wording is a mess but I hope you can follow it.)

[Robert Latest]

user923005 wrote:

user923005 <[e-mail]:
Consider:
*listA: A -- B -- C -- D * * * * * * J -- K
* * * * * * * * * * * * \ * * * * * /
* * * * * * * * * * * * *E -- F -- G
* * * * * * * * * * * * / * * * * * \
*listB: * * * * * H -- I * * * * * * |
* * * * * * * * * * * * \ * * * * * *L
* * * * * * * * * * * * * N -- M -- /

How is G's next link to both L _and_ J?

listA has nodes A,B,C,D,E,F,G,L,N,M,I
G's next link is L.

listB has nodes H,I,E,F,G,J,K
G's next link is J.

The picture above is the actual node structure, showing what is held
in common, if the graphs were actually merged.

I think you're suffering from a misconception regarding "lists". In a
single-linked list, each node has EXACTLY ONE successor, or a "next
element". (In a doubly-linked list, it also has EXACTLY ONE precedessor, but
that's not pertinent here).

Following your definition of list A, G's next element is L, and I has no
next element.

According to your def of B, there is an element I' whose next element is E,
and another one, G', whose next element is J.

Is it possible, under the condition that both definitions above hold, that
I == I' && G==G'
respectively?

Rhetorical question. The answer is no.

I was trying to point out that if we are given listA and listB as
above,

which isn't possible,

then the simple "find the node where they meet" strategy is not
going ot produce expected results.

....like so often when applying strategies to situations which cannot
exist ;-)

Do yourself a favor and actually try to implement your "convoluted list"
example in C. You'll soon find your conceptual error. You may start with a
typical list element definition like this one:

struct list_node_t {
void *data; /* pointer to payload */
struct list_node_t *next;
} ;

Of course it's possible for the 'data' pointers of nodes in disjunct lists
to point to the same 'payload' memory location (a frequent occurrence in
real code), but that's besides the point.

robert

[Flash Gordon]

user923005 wrote, On 23/01/08 06:13:

On Jan 22, 5:00 pm, Peter Nilsson <[e-mail]:

>user923005 <[e-mail]:

>>Ben Pfaff <[e-mail]:
user923005 <[e-mail]:
Consider:
listA: A -- B -- C -- D J -- K
\ /
E -- F -- G
/ \
listB: H -- I |
\ L
N -- M -- /
I don't see how this can happen in a linked list structure.
A linked list node can have only one successor, but your

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

>>>nodes I and G appear to each have two (E and N, and J and
L, respectively).
listA has nodes A,B,C,D,E,F,G,L,N,M,I
listB has nodes H,I,E,F,G,J,K
They share I,E,F,G

How is G's next link to both L _and_ J?

listA has nodes A,B,C,D,E,F,G,L,N,M,I
G's next link is L.

listB has nodes H,I,E,F,G,J,K
G's next link is J.

So how do you get J->next to hold two different values at the same time?
That, I believe, is the point that is being raised. Remember that the
node type will be something like
struck node {
struct node *next;
struct data data;
};

The picture above is the actual node structure, showing what is held
in common, if the graphs were actually merged.
I was trying to point out that if we are given listA and listB as
above, then the simple "find the node where they meet" strategy is not
going ot produce expected results. If you have some sort of merge
operation, all sorts of strange things might occur.

Ah, I think I see the difference of opinion. You are saying if the data
is the same in two different node objects then when merging the lists
you would replace them with a single object. Others have been thinking
that it does not matter what the data is, it only matters if it is
actually the same object appearing in both list. So perhaps you think of
the node structure as
struck node {
struct node *next;
struct data *data; /* This is now a pointer */
};

This means that yours is a harder problem than others have been trying
to solve.
--
Flash Gordon

[user923005]

On Jan 23, 12:33*am, Robert Latest <[e-mail]:

user923005 wrote:

user923005 <[e-mail]:
Consider:
*listA: A -- B -- C -- D * * * * * * J -- K
* * * * * * * * * * * * \ * * * ** /
* * * * * * * * * * * * *E -- F -- G
* * * * * * * * * * * * / * * * ** \
*listB: * * * * * H -- I * * * * * * |
* * * * * * * * * * * * \ * * * ** *L
* * * * * * * * * * * * * N -- M -- /

How is G's next link to both L _and_ J?

listA has nodes A,B,C,D,E,F,G,L,N,M,I
G's next link is L.

listB has nodes H,I,E,F,G,J,K
G's next link is J.

The picture above is the actual node structure, showing what is held
in common, if the graphs were actually merged.

I think you're suffering from a misconception regarding "lists". In a
single-linked list, each node has EXACTLY ONE successor, or a "next
element". (In a doubly-linked list, it also has EXACTLY ONE precedessor, but
that's not pertinent here).

True, but what if the data does not follow that pattern?

Following your definition of list A, G's next element is L, and I has no
next element.

According to your def of B, there is an element I' whose next element is E,
and another one, G', whose next element is J.

Is it possible, under the condition that both definitions above hold, that
* * I == I' && G==G'
respectively?

Rhetorical question. The answer is no.

Look again: I gave the nodes of the two lists:

listA has nodes A,B,C,D,E,F,G,L,N,M,I

listB has nodes H,I,E,F,G,J,K

I was trying to point out that if we are given listA and listB as
above,

which isn't possible,

Of course it is.

then the simple "find the node where they meet" strategy is not
going ot produce expected results.

...like so often when applying strategies to situations which cannot
exist ;-)

Do yourself a favor and actually try to implement your "convoluted list"
example in C. You'll soon find your conceptual error. You may start with a
typical list element definition like this one:

struct list_node_t {
* *void *data; /* pointer to payload */
* *struct list_node_t *next;

} ;

Of course it's possible for the 'data' pointers of nodes in disjunct lists
to point to the same 'payload' memory location (a frequent occurrence in
real code), but that's besides the point.

Believe it or not, I have written successful lists and graphs.

[guanjun]

On Jan 22, 3:19 pm, "[e-mail]"
<[e-mail]:

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 an O(N) solution without tagging or memory allocating tech.
(btw, I personally prefer the tag-the-lsb-bit-of-pointer method, which
is simple and cool.)

first, apply an known algorithm to list A to figure out the last non-
repeated node of it. Note that list A is
either a common single list (tail point to NULL) or list with a cycle.
second, apply the same algorithm to list B to figure out the last non-
repeated node, which actually is the merge node of list A and list B.
we play a trick in the second step to make list A appears like a big
cycle as a whole. that is, the code of moving p to the next node
should be like this:
p = (p == last_non_repeated_node_of_list_a) ? head_node_of_list_a : p-

>next;

description of the 'known algorithm' (find out the merge node in a
single list with a cycle):
1) let two pointer p1 and p2 point to the head node of the single
list.
2) move forward p1 one node, p2 two nodes. repeat this step until p1
== p2.
3) keep p1 still, and p2 point back to the head node of the single
list.
then move forward p1 and p2 one node each, until they meet.
the node they meet is the merge node of the single list.

[Army1987]

user923005 wrote:

On Jan 23, 12:33Â*am, Robert Latest <[e-mail]:

>user923005 wrote:

user923005 <[e-mail]:
Consider:
Â*listA: A -- B -- C -- D Â* Â* Â* Â* Â* Â* J -- K
Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* \ Â* Â* Â* Â* Â* /
Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â*E -- F -- G
Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* / Â* Â* Â* Â* Â* \
Â*listB: Â* Â* Â* Â* Â* H -- I Â* Â* Â* Â* Â* Â* |
Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* \ Â* Â* Â* Â* Â* Â*L
Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* N -- M -- /

>How is G's next link to both L _and_ J?
listA has nodes A,B,C,D,E,F,G,L,N,M,I
G's next link is L.

listB has nodes H,I,E,F,G,J,K
G's next link is J.

The picture above is the actual node structure, showing what is held
in common, if the graphs were actually merged.

I think you're suffering from a misconception regarding "lists". In a
single-linked list, each node has EXACTLY ONE successor, or a "next
element". (In a doubly-linked list, it also has EXACTLY ONE precedessor, but
that's not pertinent here).

True, but what if the data does not follow that pattern?

Then it isn't a linked list.
--
Army1987 (Replace "NOSPAM" with "email")

[Richard Bos]

Flash Gordon <sp**@flash-gordon.me.ukwrote:

user923005 wrote, On 23/01/08 06:13:

I was trying to point out that if we are given listA and listB as
above, then the simple "find the node where they meet" strategy is not
going ot produce expected results. If you have some sort of merge
operation, all sorts of strange things might occur.

Ah, I think I see the difference of opinion. You are saying if the data
is the same in two different node objects then when merging the lists
you would replace them with a single object. Others have been thinking
that it does not matter what the data is, it only matters if it is
actually the same object appearing in both list.

This means that yours is a harder problem than others have been trying
to solve.

No, what it means is that the problem _as stated_ is not quite clear
enough. It's probably clear to the person who framed it which version is
meant, but without any context, either interpretation is a valid one -
although I'd agree that the "common" interpretation is more likely the
intended one than Dann's.

Richard

[Richard Harter]

On Wed, 23 Jan 2008 02:36:19 -0800 (PST), guanjun
<gu******@gmail.comwrote:

>On Jan 22, 3:19 pm, "[e-mail]"
<[e-mail]:

>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 an O(N) solution without tagging or memory allocating tech.
(btw, I personally prefer the tag-the-lsb-bit-of-pointer method, which
is simple and cool.)

first, apply an known algorithm to list A to figure out the last non-
repeated node of it. Note that list A is
either a common single list (tail point to NULL) or list with a cycle.
second, apply the same algorithm to list B to figure out the last non-
repeated node, which actually is the merge node of list A and list B.

There is an error here. When the two lists terminate in a cycle
each list can join the cycle at different nodes. Each is a
legitimate merge node, i.e., we can follow A until it reaches B's
merge point or we can follow B until it reaches A's merge point.
There is no singular "the merge point".

One can argue that the phrasing of the original question
implicitly specified null terminated lists since it used the
wording "the intersection point". Alternatively, we can remove
the ambiguity by adopting some criterion for the "best" merge
point, e.g., the one that minimizes the combined lengths to the
merge point, although this fails if the two merge points are on
exact opposite sides of the cycle.

Even if we rule out cycles, a "good" algorithm should be able to
handle them. As it happens, the second algorithm I posted does
and will produce the "earlier" merge point.

>we play a trick in the second step to make list A appears like a big
cycle as a whole. that is, the code of moving p to the next node
should be like this:
p = (p == last_non_repeated_node_of_list_a) ? head_node_of_list_a : p-

>>next;

description of the 'known algorithm' (find out the merge node in a
single list with a cycle):
1) let two pointer p1 and p2 point to the head node of the single
list.
2) move forward p1 one node, p2 two nodes. repeat this step until p1
== p2.
3) keep p1 still, and p2 point back to the head node of the single
list.
then move forward p1 and p2 one node each, until they meet.
the node they meet is the merge node of the single list.

[Flash Gordon]

Richard Bos wrote, On 23/01/08 15:43:

Flash Gordon <sp**@flash-gordon.me.ukwrote:

<snip>

>This means that yours is a harder problem than others have been trying
to solve.

No, what it means is that the problem _as stated_ is not quite clear
enough. It's probably clear to the person who framed it which version is
meant, but without any context, either interpretation is a valid one -
although I'd agree that the "common" interpretation is more likely the
intended one than Dann's.

I did not say that the problem as stated was clearly enough, I said that
people were trying to solve different problems.
--
Flash Gordon

[Ike Naar]

In article <3d**********************************@e4g2000hsg.g ooglegroups.com>,
ju**********@yahoo.co.in <ju**********@yahoo.co.inwrote:

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.

Reverse both lists and compare the reversed lists?

[CBFalconer]

Ike Naar wrote:

ju**********@yahoo.co.in <ju**********@yahoo.co.inwrote:

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

Reverse both lists and compare the reversed lists?

Initial lists:

list1: A --B --C -\
\
--D --E
/
list2: X --Y -------/

Reverse list1 and get: (remember Ys next ptr unchanged)

list1: E -------------\
\
--D --C --B --A
/
list2: X --Y -------/

Now reverse list2 and get: (Es next ptr unchanged)

list1: E --------------\
\
--D --Y --X
/
list2: A --B --C --/

==========================================
However, if we first reverse list2, we get:

list1: A --B --C -\
\
--D --Y --X
/
list2: E -------------/

Now reverse list1 and get:

list1: X --Y -------\
\
--D --C --B --A
/
list2: E -------------/

and I cannot see what is common to the two double reversals that
identifies the original node C (or Y), nor the reversal steps need
to regain the original configuration.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

[Robert Latest]

dj******@csclub.uwaterloo.ca.invalid wrote:

If your comparison is "does this node have the same value" (checking
equivalence), you'll find a match in I-E-F-G in the original example as
well as in C-D-E in the simpler example.

Yes, but if we talk about "values" (or "payloads", as I like to call them)
of lists then the OP should have said so. I'm doubtful that he gets the
difference.

robert

[Robert Latest]

user923005 wrote:

Believe it or not, I have written successful lists and graphs.

I believe you when you show us a small example of crossing-over linked
lists.

robert

[Ike Naar]

CBFalconer <cb********@maineline.netwrote:

>Ike Naar wrote:

>Reverse both lists and compare the reversed lists?

Initial lists:

list1: A --B --C -\
\
--D --E
/
list2: X --Y -------/

[snipped: in-place place reveral list1 and list2]

and I cannot see what is common to the two double reversals that
identifies the original node C (or Y), nor the reversal steps need
to regain the original configuration.

What I actually meant to say (and I did not make myself very clear) was:
produce a reversed _copy_ of each list, and compare the reversed copies,

list1: A B C D E reversed copy of list1: E D C B A
list2: X Y D E reversed copy of list2: E D Y X
common prefix of reversed copies: E D

A far more elegant solution has been posted elsethread:
Make sure both lists have equal length, by trimming the head part of
the longest list; then find the first common element of the resulting
lists.

[Ben Bacarisse]

Robert Latest <bo*******@yahoo.comwrites:

user923005 wrote:

>Believe it or not, I have written successful lists and graphs.

I believe you when you show us a small example of crossing-over linked
lists.

I think that dcorbit is talking about lists in which the content is
pointed to by, rather than contain in, the nodes. I C:

struct list_node {
struct list_node *next;
Content *content; /* void * if one wants to be generic */
};

With this structure, two lists may share data so that diagrams in
which some items are common to multiple lists are then possible.

--
Ben.

[pete]

CBFalconer wrote:

>
Richard Heathfield wrote:

... snip ...

Indeed. Consider these linked lists:

listA: A -- B -- C -- D
\
E -- F -- G
/
listB: H -- I

You can scan through the lists. Do so, retaining L as the length
of listA, and L1 as the length of listB. Now reverse listA in
place, and remeasure the length of list B, getting L2.

In the example, L is 7, L1 is 5, L2 is 7. I think you can now find
the location of item E in either list.

If the first node of listA is node number (0),
then item E is node number (((L - L1 + L2) - 1) / 2) of listA.

--
pete

[pete]

pete wrote:

>
CBFalconer wrote:

Richard Heathfield wrote:

>

... snip ...

>
Indeed. Consider these linked lists:
>
listA: A -- B -- C -- D
\
E -- F -- G
/
listB: H -- I

You can scan through the lists. Do so, retaining L as the length
of listA, and L1 as the length of listB. Now reverse listA in
place, and remeasure the length of list B, getting L2.

In the example, L is 7, L1 is 5, L2 is 7. I think you can now find
the location of item E in either list.

If the first node of listA is node number (0),
then item E is node number (((L - L1 + L2) - 1) / 2) of listA.

That would be after listA has been reversed again.

--
pete