Velocity Reviews > linked list question

user923005
Guest
Posts: n/a

 01-22-2008
On Jan 22, 1:42*am, Richard Heathfield <(E-Mail Removed)> 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.

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
Guest
Posts: n/a

 01-22-2008
user923005 <(E-Mail Removed)> writes:

> 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
Guest
Posts: n/a

 01-22-2008
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>

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

CBFalconer
Guest
Posts: n/a

 01-22-2008
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>

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

gw7rib@aol.com
Guest
Posts: n/a

 01-22-2008
On 22 Jan, 09:42, Richard Heathfield <(E-Mail Removed)> 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.

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
Guest
Posts: n/a

 01-23-2008
(E-Mail Removed) wrote:
> Richard Heathfield <(E-Mail Removed)> wrote:
> > ... 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 *******s.

--
Peter

user923005
Guest
Posts: n/a

 01-23-2008
On Jan 22, 2:40*pm, Ben Pfaff <(E-Mail Removed)> wrote:
> user923005 <(E-Mail Removed)> writes:
> > 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
Guest
Posts: n/a

 01-23-2008
On Jan 22, 9:42*am, Richard Heathfield <(E-Mail Removed)> wrote:
> 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
Guest
Posts: n/a

 01-23-2008
user923005 <(E-Mail Removed)> wrote:
> Ben Pfaff <(E-Mail Removed)> wrote:
> > user923005 <(E-Mail Removed)> writes:
> > > 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

James Kuyper
Guest
Posts: n/a

 01-23-2008
user923005 wrote:
> On Jan 22, 2:40 pm, Ben Pfaff <(E-Mail Removed)> wrote:
>> user923005 <(E-Mail Removed)> writes:
>>> 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

Where does I's next pointer point? In ListA, it points nowhere, in
ListB, it points to E.
Where does G's next-pointer point? In ListA, it's L, in listB it's J.

As far as I can see, this can work as a linked list, bu only if the
central loop constitutes a circularly-linked (and therefore infinite)
list, and the three outside portions all link inward, toward the
circular loop. There's two solutions, depending upon whether the central
loop is linked in the clockwise or counter-clockwise direction.