Board index » delphi » How to reverse list?

How to reverse list?

I can traverse a singly linked list, and I can print in reverse, but how do I
actually reverse the nodes in the list (just a helpful hint is all I am
looking for).

TIA,
Craig.

 

Re:How to reverse list?


Quote
Craig Milne wrote:

> I can traverse a singly linked list, and I can print in reverse, but how do I
> actually reverse the nodes in the list (just a helpful hint is all I am
> looking for).

> TIA,
> Craig.

Hi

Can't you just start reading the original from the head of the list,
and for the reversed list add each node in front of the head of the
copied list?

Remco

Re:How to reverse list?


Quote
cmi...@hookup.net (Craig Milne) wrote:
>I can traverse a singly linked list, and I can print in reverse, but how do I
>actually reverse the nodes in the list (just a helpful hint is all I am
>looking for).
>TIA,
>Craig.

Of course the easiest way to do this is to make a doubly linked list
in the first place and then start from the head or tail as you choose.
Assuming you really don't want to do that for some reason, such as
running out of heap, you can convert a queue (first-in-first-out) into
a stack (last-in-first-out) and vice versa.

First let us be sure we have the same vocabulary. The following type
is a sort of "universal" node that stores one character, and one link.
That link can be either to a previous or the next node in the linked
list.

TYPE
NodeLink = ^Node;
Node = RECORD
          ch:Char;
          lnk:NodeLink;
       END;

VAR
head, tail, p1, p2, p3:NodeLink;
...

Assume we have made a queue. The characters in the list would be in
the order of entry from head to tail. lnk points to the next node
until the end of the list where tail^.lnk is NIL.

In a stack each node points to the previous node except head where
head^.lnk is NIL,

In a queue the above node could display the chars in the original
order. A stack would display them in the reverse order. A procedure
such as Display(head, tail) could take care of displaying the chars.

To covert the queue into a stack you could do somthing like the
following:

===========
     p1 := head;   p2 := p1^.lnk; (* next node in queue *)
     While p2 <> tail Do
     Begin
          p3 := p2^.lnk;   (* next node in queue *)
          p2^.lnk := p1;   (* prev node in stack *)
          p1 := p2;
          p2 := p3;
     End;
     tail^.lnk := p1;
     head^.lnk := NIL;

     DisplayList(tail, head);
===============

This leapfrogs the pointers down the queue while reversing their
aiming direction and then sets the links for tail and head.

It is highly recommended that you sketch a queue of only 4 nodes and
convince yourself that this actually works. I cheated. I made a sketch
and then wrote a program to be sure!

Regards,
Clif   <clifp...@airmail.net>   1:25PM  6/20/97

Re:How to reverse list?


Quote
cmi...@hookup.net (Craig Milne) wrote:
>I can traverse a singly linked list, and I can print in reverse, but how do I
>actually reverse the nodes in the list (just a helpful hint is all I am
>looking for).

If you can print in reverse, then begin a new empty list, then
rather than print, link the node to the head of a the new list.
When done, replace the head of the old list with that of the new
list.  Since you allocated nothing, you have nothing to dispose.

An iterative solution would be to establish two pointers. One to
mark the head of a new list, the other to mark the link to the
next node.  Initialize the new head to NIL and initialize the
other to point to the head.  Either use a third pointer or the
old pointer to the head of the old list to mark the current node
as you walk the old list.  

p1: Pointer to node = NIL;
p2: Pointer to pointer = @p1;
p3: Pointer to node = head of original list;

Now walk the old list appending each node to the new list.

  While the current pointer is not nil
  (p3 <> NIL)

    store the address of the current node to the link pointed
    to by the 2nd pointer.  (p2^ := p3)

    Set 2nd pointer to point to that node's link field.
    (p2 := @p3^.Next)

    Walk the 3rd pointer to the next field.
    (p3 := P3^.Next)
  EndWhile

  Ground the last node
  (p2^ := NIL)

Once you have completed the new list, assign the first pointer
as the head of the original list.  Since you allocated nothing,
you have nothing to dispose.

    ...red

--
Support the anti-Spam amendment
  Join at http://www.cauce.org/

Other Threads