Reversing a singly linked list

[saki]

How do we reverse a singly linked list without using extra
memory.Extra pointers can however be used

[Richard Heathfield]

saki said:

How do we reverse a singly linked list without using extra
memory.Extra pointers can however be used

Algorithm REVERSE:

Have two pointers, spare and revlist, initially both set to NULL.

Special case: if you have a list with no items, terminate (nothing to do).

Base case: If you have a list with only one item (list->next is NULL):
If revlist is NULL, set it to point to the one item.
(Otherwise, don't.)
Terminate.

Otherwise, point one of your spare pointers to the head of the list.
Iterate through the list until you're pointing at the last-but-one member
of the list. You now have a pointer (spare->next) that points to the last
member in the list. spare->next->next should be NULL. Set
spare->next->next to revlist, and then set revlist to spare->next. Set
spare->next to NULL. Execute algorithm REVERSE.

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

[CBFalconer]

saki wrote:

>
How do we reverse a singly linked list without using extra
memory. Extra pointers can however be used

/* ================================================== ===== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

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

[Gene]

On Jul 4, 9:16*am, saki <[e-mail]:

How do we reverse a singly linked list without using extra
memory.Extra pointers can however be used

In pseudo code, to reverse L, pop elements from L and push onto
(initially empty) R until L is empty. Then return R.

Now in C (untested):

NODE *rev (NODE *lst)
{
NODE *t, *rtn;

rtn = NULL;
while (lst) {

// pop
t = lst;
lst = lst->next;

// push
t->next = rtn;
rtn = t;
}
return rtn;
}

[aarklon]

On Jul 4, 6:16 pm, saki <[e-mail]:

How do we reverse a singly linked list without using extra
memory.Extra pointers can however be used

sn* reverse(sn* p)
{

sn*prev = NULL,*curr =p;
while(curr)
{
p = p -link;
curr -link = prev;
prev = curr;
curr = p;
}

return prev;
}