446,261 Members | 1,325 Online
Need help? Post your question and get tips & solutions from a community of 446,261 IT Pros & Developers. It's quick & easy.

 P: n/a How can I reverse a linked list with no memory allocation? I'm searching for an algorithm which is constant in runtime and space. Thanks Nov 13 '05 #1
9 Replies

 P: n/a Perpetual Snow wrote: How can I reverse a linked list with no memory allocation? I'm searching for an algorithm which is constant in runtime and space. That would be a neat trick (to do it in constant time), but it's not topical here. Try an algorithms group. -Kevin -- My email address is valid, but changes periodically. To contact me please use the address from a recent posting. Nov 13 '05 #2

 P: n/a On 2003-11-26, Kevin Goodsell wrote: Perpetual Snow wrote: How can I reverse a linked list with no memory allocation? I'm searching for an algorithm which is constant in runtime and space. That would be a neat trick (to do it in constant time), but it's not topical here. Try an algorithms group. Assuming something like this: typedef struct list list; typedef struct node node; node * first_node(list *); node * last_node(list *); node * next_node(node *); node * prev_node(node *); typedef struct list_interface { node * (*first_)(list *); node * (*last_)(list *); } list_interface; typedef struct node_interface { node * (*next_)(node *); node * (*prev_)(node *); } node_interface; const list_interface List = { first_node, last_node }; const node_interface Node = { next_node, prev_node }; Then reversing it is easy: const list_interface RevList = { last_node, first_node }; const node_interface RevNode = { prev_node, next_node }; -- James Nov 13 '05 #3

 P: n/a "Perpetual Snow" wrote in message news:3f***********************@news.free.fr... How can I reverse a linked list with no memory allocation? I'm searching for an algorithm which is constant in runtime and space. Walk the list, changing the pointers as you go. Nov 13 '05 #4

 P: n/a On Wed, 26 Nov 2003 03:23:09 -0600, James Hu wrote: On 2003-11-26, Kevin Goodsell wrote: Perpetual Snow wrote: How can I reverse a linked list with no memory allocation? I'm searching for an algorithm which is constant in runtime and space. That would be a neat trick (to do it in constant time), but it's not topical here. Try an algorithms group.Assuming something like this: typedef struct list list; typedef struct node node; node * first_node(list *); node * last_node(list *); node * next_node(node *); node * prev_node(node *); typedef struct list_interface { node * (*first_)(list *); node * (*last_)(list *); } list_interface; typedef struct node_interface { node * (*next_)(node *); node * (*prev_)(node *); } node_interface; const list_interface List = { first_node, last_node }; const node_interface Node = { next_node, prev_node };Then reversing it is easy: const list_interface RevList = { last_node, first_node }; const node_interface RevNode = { prev_node, next_node };-- James James, I think you read ahead. His class hasn't learned about doubly linked lists yet! - Sev Nov 13 '05 #5

 P: n/a J. J. Farrell wrote: "Perpetual Snow" wrote in message news:3f***********************@news.free.fr...How can I reverse a linked list with no memory allocation?I'm searching for an algorithm which is constant in runtime and space. Walk the list, changing the pointers as you go. And that is supposed to be constant in time? Nov 13 '05 #6

 P: n/a Just curious wrote: J. J. Farrell wrote: "Perpetual Snow" wrote in message news:3f***********************@news.free.fr...How can I reverse a linked list with no memory allocation?I'm searching for an algorithm which is constant in runtime and space. Walk the list, changing the pointers as you go. And that is supposed to be constant in time? That's easily achived, assuming the implementation has a limit on the length of a linked list. -- Chris "the impossible we relabel at once" Dollin C FAQs at: http://www.faqs.org/faqs/by-newsgrou...mp.lang.c.html C welcome: http://www.angelfire.com/ms3/bchambl...me_to_clc.html Nov 13 '05 #7

 P: n/a Perpetual Snow wrote: How can I reverse a linked list with no memory allocation? I'm searching for an algorithm which is constant in runtime and space. It obviously cannot execute in constant time. An O(n) process is: /* The bare minimum to form a linked list */ typedef struct node { struct node *next; void *data; } node, *nodeptr; /* ================================================== ===== */ /* 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 */ -- Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net) Available for consulting/temporary embedded and systems. USE worldnet address! Nov 13 '05 #8

 P: n/a On Wed, 26 Nov 2003 10:33:46 +0000, Chris Dollin wrote: Just curious wrote: J. J. Farrell wrote: "Perpetual Snow" wrote in message news:3f***********************@news.free.fr...How can I reverse a linked list with no memory allocation?I'm searching for an algorithm which is constant in runtime and space. Walk the list, changing the pointers as you go. And that is supposed to be constant in time? That's easily achived, assuming the implementation has a limit on the length of a linked list. Now THAT is funny. ;-) Mac -- Nov 13 '05 #9

 P: n/a # 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 */ for (prev=0,curr=list; curr; prev=curr,curr=next) { next = curr->next; curr->next = prev; } list = prev; -- Derk Gwen http://derkgwen.250free.com/html/index.html I love the smell of commerce in the morning. Nov 13 '05 #10

### This discussion thread is closed

Replies have been disabled for this discussion.