reverse a single linked list

Discussion in 'C Programming' started by sam_cit@yahoo.co.in, Dec 17, 2006.

  1. Guest

    Hi Everyone,

    I want to actually reverse a single linked list without using many
    variables, i have a recurssive solution, but i wanted an iterative one.
    can anyone help me on this?
     
    , Dec 17, 2006
    #1
    1. Advertising

  2. Ico Guest

    wrote:
    > Hi Everyone,
    >
    > I want to actually reverse a single linked list without using many
    > variables, i have a recurssive solution, but i wanted an iterative one.


    Why would you want that, is your recursive solution not good enough ?

    --
    :wq
    ^X^Cy^K^X^C^C^C^C
     
    Ico, Dec 17, 2006
    #2
    1. Advertising

  3. Guest


    >
    > Why would you want that, is your recursive solution not good enough ?
    >


    Yes, recursive solution is good but uses a lot of stack space and it
    might not be helpful in a envirnoment where stack space is limited like
    embedded systems where recursive functions are normally not encouraged.
     
    , Dec 17, 2006
    #3
  4. Ico Guest

    wrote:
    >
    >>
    >> Why would you want that, is your recursive solution not good enough ?
    >>

    >
    > Yes, recursive solution is good but uses a lot of stack space and it
    > might not be helpful in a envirnoment where stack space is limited like
    > embedded systems where recursive functions are normally not encouraged.


    Use a doubly linked list then.


    -
    :wq
    ^X^Cy^K^X^C^C^C^C
     
    Ico, Dec 17, 2006
    #4
  5. Eric Sosman Guest

    wrote:
    > Hi Everyone,
    >
    > I want to actually reverse a single linked list without using many
    > variables, i have a recurssive solution, but i wanted an iterative one.
    > can anyone help me on this?


    Since this has the odor of homework about it, I'll just
    offer a few hints:

    Hint #1: Do you know how to remove the first item from
    a linked list?

    Hint #2: Do you know how to add an item at the beginning
    of a linked list?

    --
    Eric Sosman
    lid
     
    Eric Sosman, Dec 17, 2006
    #5
  6. Guest


    >
    > Hint #2: Do you know how to add an item at the beginning
    > of a linked list?
    >
    > --


    Thanks very much for the hints, did you mean to say add an item at the
    end of the list?

    >From your hints, i think of a solution where in the last_node->ptr is

    made to point to first node and this logic needs to be excecuted as
    many times as many as strlen(string). Is this the solution you meant or
    any other improvements are possible?
     
    , Dec 17, 2006
    #6
  7. Eric Sosman Guest

    wrote:
    >> Hint #2: Do you know how to add an item at the beginning
    >> of a linked list?
    >>
    >> --

    >
    > Thanks very much for the hints, did you mean to say add an item at the
    > end of the list?


    Hint #3: No.

    >>From your hints, i think of a solution where in the last_node->ptr is

    > made to point to first node and this logic needs to be excecuted as
    > many times as many as strlen(string). Is this the solution you meant or
    > any other improvements are possible?


    No, and yes.

    You are working too hard: There exists a much simpler
    solution than those you seem to be thinking about.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Dec 17, 2006
    #7
  8. Guest

    >
    > >>From your hints, i think of a solution where in the last_node->ptr is

    > > made to point to first node and this logic needs to be excecuted as
    > > many times as many as strlen(string). Is this the solution you meant or
    > > any other improvements are possible?

    >
    > No, and yes.
    >
    > You are working too hard: There exists a much simpler
    > solution than those you seem to be thinking about.
    >


    Yeah, i think so, i just got a solution but i don't think it utilises
    your hints, it goes like this

    reverse(stuct list* node)
    {
    struct list* original_head = node;
    struct list* new_head = NULL;
    struct list* original_head_next = NULL;

    while(original_head != NULL)
    {
    original_head_next = original_head->ptr;
    origianl_head->ptr = new_head;
    new_head = original_head;
    original_head = original_head_next;
    }

    return(new_head);

    }

    Did you mean any other solution???
     
    , Dec 17, 2006
    #8
  9. pete Guest

    Ico wrote:
    >
    > wrote:
    > >
    > >>
    > >> Why would you want that,
    > >> is your recursive solution not good enough ?
    > >>

    > >
    > > Yes, recursive solution is good but uses a lot of stack space and it
    > > might not be helpful in a envirnoment
    > > where stack space is limited like
    > > embedded systems where recursive
    > > functions are normally not encouraged.

    >
    > Use a doubly linked list then.


    A doubly linked list has nothing to do with OP's stated problem.

    --
    pete
     
    pete, Dec 17, 2006
    #9
  10. Eric Sosman Guest

    wrote:
    >>> >From your hints, i think of a solution where in the last_node->ptr is
    >>> made to point to first node and this logic needs to be excecuted as
    >>> many times as many as strlen(string). Is this the solution you meant or
    >>> any other improvements are possible?

    >> No, and yes.
    >>
    >> You are working too hard: There exists a much simpler
    >> solution than those you seem to be thinking about.
    >>

    >
    > Yeah, i think so, i just got a solution but i don't think it utilises
    > your hints, it goes like this
    >
    > reverse(stuct list* node)
    > {
    > struct list* original_head = node;
    > struct list* new_head = NULL;
    > struct list* original_head_next = NULL;
    >
    > while(original_head != NULL)
    > {
    > original_head_next = original_head->ptr;
    > origianl_head->ptr = new_head;
    > new_head = original_head;
    > original_head = original_head_next;
    > }
    >
    > return(new_head);
    >
    > }
    >
    > Did you mean any other solution???


    That's the one I meant, although I would have written it
    with fewer auxiliary variables. One way to look at this
    approach is to think of it as removing the first node from
    the old list (hint #1) and pushing it onto the start of the
    new list (hint #2), and repeating until the old list is empty.

    Start:
    old -> A -> B -> C ->|
    new ->|

    Step 1:
    old -> B -> C ->|
    new -> A ->|

    Step 2:
    old -> C ->|
    new -> B -> A ->|

    Step 3:
    old ->|
    new -> C -> B -> A ->|

    Or, to relate it to another common experience: Hold a
    deck of playing cards face down, and deal the cards one at
    a time (still face down) onto a pile on the table in front
    of you. How does the order of the cards in the dealt pile
    relate to the order in the original deck?

    --
    Eric Sosman
    lid
     
    Eric Sosman, Dec 17, 2006
    #10
  11. CBFalconer Guest

    wrote:
    >
    > I want to actually reverse a single linked list without using many
    > variables, i have a recurssive solution, but i wanted an iterative
    > one. can anyone help me on this?


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

    which requires that a 'nodeptr' be defined to point to a struct
    with at least a next field, of type nodeptr. Usage is of the form:

    nodeptr root;
    ....
    /* code to form the list */
    ...
    root = revlist(root)

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>
     
    CBFalconer, Dec 18, 2006
    #11
  12. Randy Howard Guest

    Ico wrote
    (in article
    <45855c89$0$18264$4all.nl>):

    > wrote:
    >>
    >>>
    >>> Why would you want that, is your recursive solution not good enough ?
    >>>

    >>
    >> Yes, recursive solution is good but uses a lot of stack space and it
    >> might not be helpful in a envirnoment where stack space is limited like
    >> embedded systems where recursive functions are normally not encouraged.

    >
    > Use a doubly linked list then.


    Wasting space on unneeded links is also frowned upon in the
    embedded space.



    --
    Randy Howard (2reply remove FOOBAR)
    "The power of accurate observation is called cynicism by those
    who have not got it." - George Bernard Shaw
     
    Randy Howard, Dec 18, 2006
    #12
    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. Perpetual Snow

    Reverse a linked list

    Perpetual Snow, Nov 26, 2003, in forum: C Programming
    Replies:
    9
    Views:
    3,331
    Derk Gwen
    Nov 27, 2003
  2. RAJASEKHAR KONDABALA

    Reverse search in a singly-linked list

    RAJASEKHAR KONDABALA, Dec 24, 2003, in forum: C Programming
    Replies:
    20
    Views:
    5,829
    saadbinsaulat
    Feb 27, 2011
  3. Daniel
    Replies:
    5
    Views:
    384
  4. fool
    Replies:
    14
    Views:
    513
    Barry Schwarz
    Jul 3, 2006
  5. joshd
    Replies:
    12
    Views:
    675
    John Carson
    Oct 2, 2006
Loading...

Share This Page