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