Reverse a linked list

Discussion in 'C Programming' started by Perpetual Snow, Nov 26, 2003.

  1. 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
     
    Perpetual Snow, Nov 26, 2003
    #1
    1. Advertising

  2. 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.
     
    Kevin Goodsell, Nov 26, 2003
    #2
    1. Advertising

  3. Perpetual Snow

    James Hu Guest

    On 2003-11-26, Kevin Goodsell <> 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 Hu, Nov 26, 2003
    #3
  4. "Perpetual Snow" <> wrote in message
    news:3fc46186$0$27027$...
    >
    > 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.
     
    J. J. Farrell, Nov 26, 2003
    #4
  5. Perpetual Snow

    Severian Guest

    On Wed, 26 Nov 2003 03:23:09 -0600, James Hu <>
    wrote:

    >On 2003-11-26, Kevin Goodsell <> 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
     
    Severian, Nov 26, 2003
    #5
  6. Perpetual Snow

    Just curious Guest

    J. J. Farrell wrote:
    > "Perpetual Snow" <> wrote in message
    > news:3fc46186$0$27027$...
    >
    >>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?
     
    Just curious, Nov 26, 2003
    #6
  7. Perpetual Snow

    Chris Dollin Guest

    Just curious wrote:

    > J. J. Farrell wrote:
    >> "Perpetual Snow" <> wrote in message
    >> news:3fc46186$0$27027$...
    >>
    >>>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-newsgroup/comp/comp.lang.c.html
    C welcome: http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html
     
    Chris Dollin, Nov 26, 2003
    #7
  8. Perpetual Snow

    CBFalconer Guest

    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 () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Nov 26, 2003
    #8
  9. Perpetual Snow

    Mac Guest

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

    > Just curious wrote:
    >
    >> J. J. Farrell wrote:
    >>> "Perpetual Snow" <> wrote in message
    >>> news:3fc46186$0$27027$...
    >>>
    >>>>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
    --
     
    Mac, Nov 27, 2003
    #9
  10. Perpetual Snow

    Derk Gwen Guest

    # 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.
     
    Derk Gwen, Nov 27, 2003
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. RAJASEKHAR KONDABALA

    Reverse search in a singly-linked list

    RAJASEKHAR KONDABALA, Dec 24, 2003, in forum: C Programming
    Replies:
    20
    Views:
    5,831
    saadbinsaulat
    Feb 27, 2011
  2. Daniel
    Replies:
    5
    Views:
    385
  3. fool
    Replies:
    14
    Views:
    515
    Barry Schwarz
    Jul 3, 2006
  4. reverse a single linked list

    , Dec 17, 2006, in forum: C Programming
    Replies:
    11
    Views:
    695
    Randy Howard
    Dec 18, 2006
  5. joshd
    Replies:
    12
    Views:
    675
    John Carson
    Oct 2, 2006
Loading...

Share This Page