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

[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(listAnodecoun t *
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].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.

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].i nvalidwrote:

... 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(listAnodecoun t * 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] rd.eduwrote:

user923005 <dcor...@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).

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].i nvalidwrote:

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.

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 <dcor...@connx. comwrote:

Ben Pfaff <[e-mail] rd.eduwrote:

user923005 <dcor...@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).

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

user923005 <dcor...@connx. comwrote:

Ben Pfaff <[e-mail] rd.eduwrote:

user923005 <dcor...@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).

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 <cbfalco...@yah oo.comwrote:

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.