Reverse a linked list

[Perpetual Snow]

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

[Kevin Goodsell]

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.

[James Hu]

On 2003-11-26, Kevin Goodsell <us************ *********@never box.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

[J. J. Farrell]

"Perpetual Snow" <pi******@hotma il.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.

[Severian]

On Wed, 26 Nov 2003 03:23:09 -0600, James Hu <jx*@despammed. com>
wrote:

On 2003-11-26, Kevin Goodsell <us************ *********@never box.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

[Just curious]

J. J. Farrell wrote:

"Perpetual Snow" <pi******@hotma il.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?

[Chris Dollin]

Just curious wrote:

J. J. Farrell wrote:

"Perpetual Snow" <pi******@hotma il.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

[CBFalconer]

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********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Mac]

On Wed, 26 Nov 2003 10:33:46 +0000, Chris Dollin wrote:

Just curious wrote:

J. J. Farrell wrote:

"Perpetual Snow" <pi******@hotma il.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
--

[Derk Gwen]

# 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=li st; 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.