Velocity Reviews > Reverse a linked list

Perpetual Snow
Guest
Posts: n/a

 11-26-2003
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
Guest
Posts: n/a

 11-26-2003
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.

James Hu
Guest
Posts: n/a

 11-26-2003
On 2003-11-26, Kevin Goodsell <(E-Mail Removed)> 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
Guest
Posts: n/a

 11-26-2003

"Perpetual Snow" <(E-Mail Removed)> wrote in message
news:3fc46186\$0\$27027\$(E-Mail Removed)...
>
> 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
Guest
Posts: n/a

 11-26-2003
On Wed, 26 Nov 2003 03:23:09 -0600, James Hu <(E-Mail Removed)>
wrote:

>On 2003-11-26, Kevin Goodsell <(E-Mail Removed)> 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,

lists yet!

- Sev

Just curious
Guest
Posts: n/a

 11-26-2003

J. J. Farrell wrote:
> "Perpetual Snow" <(E-Mail Removed)> wrote in message
> news:3fc46186\$0\$27027\$(E-Mail Removed)...
>
>>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
Guest
Posts: n/a

 11-26-2003
Just curious wrote:

> J. J. Farrell wrote:
>> "Perpetual Snow" <(E-Mail Removed)> wrote in message
>> news:3fc46186\$0\$27027\$(E-Mail Removed)...
>>
>>>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

--
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
Guest
Posts: n/a

 11-26-2003
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 ((E-Mail Removed)) ((E-Mail Removed))
Available for consulting/temporary embedded and systems.

Mac
Guest
Posts: n/a

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

> Just curious wrote:
>
>> J. J. Farrell wrote:
>>> "Perpetual Snow" <(E-Mail Removed)> wrote in message
>>> news:3fc46186\$0\$27027\$(E-Mail Removed)...
>>>
>>>>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
Guest
Posts: n/a

 11-27-2003
# 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.