Reversing a singly linked list

Discussion in 'C Programming' started by saki, Jul 4, 2008.

  1. saki

    saki Guest

    How do we reverse a singly linked list without using extra
    memory.Extra pointers can however be used
     
    saki, Jul 4, 2008
    #1
    1. Advertising

  2. saki

    Gene Guest

    On Jul 4, 9:16 am, saki <> wrote:
    > How do we reverse a singly linked list without using extra
    > memory.Extra pointers can however be used


    In pseudo code, to reverse L, pop elements from L and push onto
    (initially empty) R until L is empty. Then return R.

    Now in C (untested):

    NODE *rev (NODE *lst)
    {
    NODE *t, *rtn;

    rtn = NULL;
    while (lst) {

    // pop
    t = lst;
    lst = lst->next;

    // push
    t->next = rtn;
    rtn = t;
    }
    return rtn;
    }
     
    Gene, Jul 5, 2008
    #2
    1. Advertising

  3. saki

    Guest

    On Jul 4, 6:16 pm, saki <> wrote:
    > How do we reverse a singly linked list without using extra
    > memory.Extra pointers can however be used


    sn* reverse(sn* p)
    {

    sn*prev = NULL,*curr =p;
    while(curr)
    {
    p = p -> link;
    curr -> link = prev;
    prev = curr;
    curr = p;
    }

    return prev;
    }
     
    , Jul 6, 2008
    #3
    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. Patrick McCourt

    Stack & Singly Linked List Data Structures

    Patrick McCourt, May 24, 2004, in forum: Java
    Replies:
    2
    Views:
    942
    Kenneth P. Turvey
    May 24, 2004
  2. HS-MOON
    Replies:
    4
    Views:
    612
    Method Man
    Sep 24, 2004
  3. CR

    AlphaSort for singly linked list

    CR, Dec 15, 2003, in forum: C Programming
    Replies:
    1
    Views:
    519
    CBFalconer
    Dec 15, 2003
  4. RAJASEKHAR KONDABALA

    Reverse search in a singly-linked list

    RAJASEKHAR KONDABALA, Dec 24, 2003, in forum: C Programming
    Replies:
    20
    Views:
    5,852
    saadbinsaulat
    Feb 27, 2011
  5. Anando

    pruning a linear singly linked list

    Anando, Apr 23, 2006, in forum: C Programming
    Replies:
    59
    Views:
    1,254
    Richard Bos
    Apr 28, 2006
Loading...

Share This Page