Reverse a Linked-List

Question: Reverse a Linked-list. Write code in C.

Answer: There are multiple ways to go about this. Let’s first look at a recursive solution.

Node * reverse( Node * ptr , Node * previous)
{
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        return ptr;
    } else {
        temp = reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
    }
}
reversedHead = reverse(head, NULL);

Now for a non-recursive solution.

Node * reverse( Node * ptr )
{
    Node * temp;
    Node * previous = NULL;
    while(ptr != NULL) {
        temp = ptr->next;
        ptr->next = previous;
        previous = ptr;
        ptr = temp;
    }
    return previous;
}

I personally prefer the non-recursive solution but it is always good to know both of them.

If anyone has any modifications or a better methods, please post it up. Comments are always welcome.

25 Responses

  1. Ali says:

    this is the simple and working code to reverse singly linked list.

    void list::rev()
    {
    node *cur,*temp,*first;
    first=h;

    cur=t;
    t=h;
    while(first!=NULL)
    {

    temp=first;

    temp->next=cur;
    cur=temp;

    }
    h=cur;
    }

  2. Tushar says:

    Node * reverse(Node * cur) {
    if(cur->next==NULL) return cur;
    Node *tmp = rreverse(cur->next);
    cur->next->next = cur;
    cur->next = NULL;
    return tmp;
    }

  3. Dipendu says:

    I am posting Rifat Nabi’s solution (above) with a bug fix:

    STUDENT_PTR ReverseList2(STUDENT_PTR cur)
    {
    STUDENT_PTR tmp;
    if(cur->nextStudent==NULL) return cur;
    tmp = ReverseList2(cur->nextStudent);
    cur->nextStudent->nextStudent = cur;
    cur->nextStudent = NULL;
    return tmp;
    }

  4. ammrin says:

    nice explanation bt if u would have visualised it , it would have been much easier.

  5. abdul says:

    steps are followed:
    1)removing the node from p;
    2)add at begening to the q;
    3)doing untill p becomes the null;
    void reverse(sll_t **ppHead)
    {
    sll_t *p=*ppHead,*q=0,*r=0;
    while(p!=NULL)
    {
    r=q;
    q=p;
    p=p->pNext;
    q->pNext=r;
    }
    *ppHead=q;
    return q;
    }

  6. kireeti says:

    hey this works really fine.. the head must be the global variable..
    void reverse(struct node *p,struct node*q)
    {

    if(q->next==null)
    {
    root=q;
    q->next=p;
    return;
    }
    else{
    reverse(q,q->next);
    q->next=p;

    }
    }

  7. @ambot..we have already discuss the reverse linked list but we cant understand what our professor was talking about. so, no comment. :)

  8. HI this is my solution using 3 pinters :-
    void reverselist(node * start)
    {
    node * t,* t1,*t2;
    if(start==NULL)
    return;

    t=NULL;
    t1=start;
    t2=t1->next;

    while(t2)
    {

    t1->next=t;
    t=t1;
    t1=t2;
    t2=t1->next;

    }
    t1->next=t;
    start=t1;

    }

  9. Hmm Nice Solutions….Thanks all of you,,

  10. arun says:

    In Java

    Node temp, prev;
    while(node.next() != null){
    temp = node.next();
    node.next() = prev;
    prev = node;
    node = temp;
    }

  11. Pedro says:

    @Rafit

    You forgot to zero out the final element’s next pointer. Really good helper function though

  12. Anonymous says:

    @Rifat

    This will produce a list with a loop at the end.

  13. Rifat Nabi says:


    Node * reverse(Node * cur) {
    if(cur->next==NULL) return cur;
    Node *tmp = rreverse(cur->next);
    cur->next->next = cur;
    return tmp;
    }

  14. DRM says:

    Actually, the non-recursive solution DOES work if you pass in the head of the list as the function argument. A good way to visualize it is to draw some arrows between some numbered nodes and keep track of which node each node pointer is currently pointing to. As you iterate through the loop, your arrows will change direction, hence reversing your list. When the loop is done, ptr and temp will both point to null, and previous will point to the start(head) of your reversed list.

    I haven’t worked through the recursive solution yet, so no comment on that.

  15. JiansNet says:

    haha, loves this question.

    My take is, two ways to do it. One is to form a new list from the old list, removing the head element each time from old list and add to new list.

    Second way, keep 3 pointers, prev, this, next, everytime move these 3 pointers one element ahead, and assign the this element with the previous element’s address.

  16. Shardul Jain says:

    I coded this. runs fine.

    Node* reverse(node *hed, node *prev)
    {
    node *tmp;
    tmp=hed->next;
    hed->next=prev;
    if(tmp!=NULL)
    {
    hed=reverse(tmp,hed);
    }
    return hed;
    }

  17. durga says:

    The recursion one seems to have some issues.
    this one works.
    Node* SingleLinkedList::RecursiveReverse(Node* pNode, Node* pPrev)
    {
    //cout <id” <id <pNext == NULL)
    {
    pNode->pNext = pPrev;
    pHead = pNode;
    return pPrev;
    }
    else
    {
    pTemp = RecursiveReverse(pNode->pNext, pNode);
    //cout <id ” <id <pNext = pPrev;
    return pPrev;
    }
    }

  18. Polaris says:

    Thanks Aswin, this is the best solution I have seen for this topic.

  19. xx says:

    This very question was on Microsoft interview.

  20. EvanM says:

    I didn’t know that gcc could perform TCO; that’s pretty cool. I’d still go for the iterative approach, though, since TCO is not part of any C standard (and there aren’t any serious benefits to the recursive version that warrant it being non-portable).

  21. Peter says:

    @EvanM A good compiler should be able to convert a tail recursive function (like the one I provided) into a function using constant stack space. Tail recursion

  22. EvanM says:

    While the recursive solution is something of an interesting novelty, it seems like it is a disaster waiting to happen. If I was the user of the recursive reverse function, I certainly would be very surprised to find out the hard way that it could reverse one linked list, but another (slightly larger) linked list caused a stack overflow.

  23. Peter says:

    I think this is simpler.

    Node * reverse(Node * head, Node * acc) {
    if(head == NULL) {
    return acc;
    } else {
    Node * tmp = head->next;
    head->next = acc;
    return reverse(tmp, head);
    }
    }

  24. Aswin says:

    Hey Matt, thanks for pointing it out. Now I know not to write posts at 2am… :) Updated the code.

  25. Matt Brubeck says:

    Your non-recursive solution does not work. It never assigns anything to “previous”, so it always returns NULL and sets all of the “next” pointers to NULL.

    Your recursive solution also does not work. It never sets “next” to NULL for the original head of the list, so now the list ends with a cycle.

    This is easy to see if you actually compile and run both of these on some simple example input.

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>