cpppro

Reversing single linked list recursively

In Algorithms, C Tidbits, Data Structures in C/C++ on March 30, 2007 at 3:30 pm

Here is the routine for reversing single linked list recursively, for reversing iteratively see the earlier post . For reversing circular single linked list visit this post. This routine takes a single linked list as argument and reverse it and returns back the head node to the reversed list.

 

please refer http://www.refcode.net/2013/02/reversing-single-linked-list-recursively.html

Advertisements
  1. Nice recursive code for reversing the linked list!
    since recursive calls uses stack the stack version for the same is mind blowing!

  2. Really mind blowing implementation.The way the “node” and “node->next” pointers are used in this implementation is amazing.

  3. I can only guess that the previous comments were ironic…

    The implementation crashes if the list is empty, does not work in a multithreaded system, and is far from elegant.

    Consider:

    /* helper func */
    struct Node* reverse(struct Node* current, struct Node* previous)
    {
    struct Node* next = current->next;
    current->next = previous;
    if (next)
    {
    return reverse(next, current);
    }
    return current;
    }

    struct Node* reverse(struct Node* aHead)
    {
    if (aHead)
    {
    return reverse(aHead, NULL);
    {
    return NULL;
    }

  4. Hi Aksu,
    >The implementation crashes if the list is empty
    Yes, it crashes for empty list, it was just an overlook, and simple check should suffice to stop that
    >does not work in a multithreaded system
    I didn’t claim that it works for multithread env, if I would have intention of multithread env, i would have not used static variables.. surprisingly your version also suffers from empty list crash scenario.
    Anyways thanks for pointing out that bug.

  5. I tried the piece of code by “ponnada” on a solaris platform just to see the result……
    Segmentation Fault(coredump)
    aftab

  6. aftab,
    I’d not given complete code (only reverse function I gave) not sure how you made a complete piece of code (by writing yours or plugging from other artilces) and not sure how you run, here I’m gibing complete code
    complete code
    I’m not facing any problems, let me know
    if you face any problems further

  7. Why static??

  8. i tried but it did not run

  9. There is a typo in the code. Just change

    void reverse(struct node** headRef)
    to
    void reverse(struct Node** headRef)

    and in main use
    reverse(&h);
    instead of
    h = recreverse(h);

    It runs now.

    I’m interested how is it possible to implement function that will reverse the order of the elements of single linked list in one pass without recursion and helper structures.

    Anyone?

    BTW. Example is very nice.

  10. I guess I’m to tired. I ment DLList but you have it already here.
    Keep up the good work.

  11. Also interested in swaping elements of SLL and DLL (changing pointers based) and sorting the list using insertion sort after the lists are created.
    Anyone worked on this…

  12. I’ guess I’m posting in a wrong thread.
    The fix is is for reverse function which is not recursive.
    Sorry.

  13. NODEPTR Reverse(NODEPTR n)
    {
    NODEPTR m;

    if(!(n && n->next))
    return n;

    m = Reverse(n->next);
    n->next->next = n;
    n->next = NULL;
    return m;
    }

    I think this should work..

  14. reverse function returns struct node, but the reverse call made in the function does not return any value.

    I doubt, if this would work.

  15. By using recursively call with only one param, I don’t know how you maintain the previous node so that the current node (whithin the current recursive call routine) ‘s next pointer can point to.

    else
    {
    headnode = node;
    tmpnode = headnode;
    }

    tmpnode->next = NULL;

    The last node doesn’t execute recursive call which is ok to terminate ,but tempnode->next = null has no point to making the list reversed at all 😦

  16. I think this should work (c#)

    Node ReverseLLS(Node node)
    {
    if (node == null) {return null;}
    if(node.Next == null){return node;}
    Node temp = node;
    node = ReverseLLS(node.Next);
    node.Next = temp;
    temp.Next = null;
    return temp;
    }

    We can use two param such as (Node current, Node previous) to implement exactly the same with \”while loop\” version.

  17. The following code NOT use static variables:
    PNode RecurReverseLink( PNode L )
    {
    if( L == NULL )
    {
    return L;
    }
    if( L->next == NULL )
    {
    return L;
    }
    PNode p = L->next;
    PNode newHead = RecurReverseLink( L->next );
    p->next = L;
    L->next = NULL;
    L = newHead;
    return L;
    }

  18. typedef struct node
    {
    int data;
    struct node* next;
    } Node;

    Node* ReverseLL (Node* current)
    {
    static Node* newHead = NULL;
    static Node* next = NULL;

    if (!current)
    { return newHead; }
    else
    {
    next = current->next;
    current->next = newHead;
    newHead = current;
    current = next;
    ReverseLL (current);
    }
    }

  19. //Correct code for single LL reversal:

    typedef struct sll
    {
    int val;
    struct sll *next;
    }SLL;

    SLL* reverse(SLL* node,SLL** newhead)
    {
    SLL* tmp=NULL;

    if(!node)
    return node;

    if(node->next)
    {
    tmp = reverse(node->next,newhead);
    tmp->next = node;
    tmp = tmp->next;
    tmp->next = NULL;
    return tmp;
    }
    else
    {
    (*newhead) = node;
    tmp = node;
    return tmp;
    }
    }

    int main()
    {
    SLL *head;
    //create a linked list here

    SLL *newhead = NULL;/* this contains head of reversed linked list*/

    reverse(head,&newhead);//done

    }

    ———————————————
    ~Sachin

  20. In ADA, 😉
    with Listas; use Listas;
    procedure Invertir (Lista : in out P_Nodo_Simple) is
    Invertida, Iterador : P_Nodo_Simple;
    begin
    — Mientras haya lista y no llegemos al final
    if Lista /= null and then Lista.Siguiente /= null then
    — llamaremos recursivamente con el lista.siguiente
    Invertir (Lista.Siguiente);
    — guardaremos la referencia al resto de la lista
    Invertida := Lista.Siguiente;
    — separamos el primer nodo, del resto de la lista
    Lista.Siguiente := null;
    — apunta al principio de la nueva lista
    — quitandole el primer nodo
    Iterador := Invertida;
    — y lo vamos colocando al final de la lista
    if Iterador /= null then
    while Iterador.Siguiente /= null loop
    Iterador := Iterador.Siguiente;
    end loop;
    Iterador.Siguiente := Lista;
    end if;
    Lista := Invertida;
    end if;
    end Invertir;

  21. void linkedlist::Reverse(node *_head)
    {
    if((_head == NULL) || (_head->next == NULL))
    head = _head;
    else
    {
    Reverse(_head->next);
    _head->next->next = _head;
    }

    // last one
    if(head != _head)
    _head->next = NULL;
    }

    This works

  22. forgot to mention:

    “head” is member of class linkedlist which
    points to the head of the list when its created.

  23. node* Recursive-Reverse(node* p)
    node* head = p
    if(p != null)
    head = Recursive-Reverse(p->next)
    if p->next == null
    head = p
    else
    p->next->next = p
    p->next = NIL
    return head;

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: