435,135 Members | 1,135 Online
+ 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
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 Email: -http://www. +rjh@ Google users: "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]: Try the download section. Jul 4 '08 #3

 P: n/a On Jul 4, 9:16*am, saki next; // push t->next = rtn; rtn = t; } return rtn; } Jul 5 '08 #4

 P: n/a On Jul 4, 6:16 pm, saki

### This discussion thread is closed

Replies have been disabled for this discussion.