By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,135 Members | 1,135 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,135 IT Pros & Developers. It's quick & easy.

Reversing a singly linked list

P: n/a
How do we reverse a singly linked list without using extra
memory.Extra pointers can however be used
Jul 4 '08 #1
Share this Question
Share on Google+
4 Replies


P: n/a
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
Jul 4 '08 #2

P: n/a
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.

Jul 4 '08 #3

P: n/a
On Jul 4, 9:16*am, saki <sakethstud...@gmail.comwrote:
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;
}
Jul 5 '08 #4

P: n/a
On Jul 4, 6:16 pm, saki <sakethstud...@gmail.comwrote:
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;
}
Jul 6 '08 #5

This discussion thread is closed

Replies have been disabled for this discussion.