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]

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

 

[James Hu]

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]

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]

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]

Walk the list, changing the pointers as you go.

And that is supposed to be constant in time?

 

[Chris Dollin]

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.

 

[CBFalconer]

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 */

 

[Mac]

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=list; curr; prev=curr,curr=next) {
next = curr->next; curr->next = prev;
}
list = prev;