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.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post RAJASEKHAR KONDABALA C Programming 20 02-27-2011 12:53 PM sam_cit@yahoo.co.in C Programming 11 12-18-2006 10:04 PM joshd C++ 12 10-02-2006 08:57 AM fool C Programming 14 07-03-2006 12:29 AM Daniel C Programming 5 10-27-2004 10:16 PM