Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > linked list question

Reply
Thread Tools

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"
> > 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.
 
Reply With Quote
 
 
 
 
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_
 
Reply With Quote
 
 
 
 
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>
Try the download section.


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

 
Reply With Quote
 
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>
Try the download section.



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

 
Reply With Quote
 
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"
> > 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.
 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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.
 
Reply With Quote
 
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
 
Reply With Quote
 
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Airplane Program with Linked Lists. The linked list portion is veryconfusing to me. jawdoc C++ 9 03-10-2008 03:38 AM
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments