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

Reverse a linked list

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
Share this Question
Share on Google+
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 <us*********************@neverbox.com> 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" <pi******@hotmail.com> 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 <jx*@despammed.com>
wrote:
On 2003-11-26, Kevin Goodsell <us*********************@neverbox.com> 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" <pi******@hotmail.com> 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" <pi******@hotmail.com> 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.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 13 '05 #8

P: n/a
Mac
On Wed, 26 Nov 2003 10:33:46 +0000, Chris Dollin wrote:
Just curious wrote:
J. J. Farrell wrote:
"Perpetual Snow" <pi******@hotmail.com> 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.