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

### Like this:

Like Loading...

*Related*

Nice recursive code for reversing the linked list!

since recursive calls uses stack the stack version for the same is mind blowing!

18 April 2007at2pmReally mind blowing implementation.The way the “node” and “node->next” pointers are used in this implementation is amazing.

30 May 2007at1pmI 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;

}

17 April 2008at2pmHi 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.

17 April 2008at7pmI tried the piece of code by “ponnada” on a solaris platform just to see the result……

Segmentation Fault(coredump)

aftab

29 April 2008at2pmaftab,

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

30 April 2008at10amWhy static??

8 May 2008at12pmi tried but it did not run

5 June 2008at6pmThere 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.

25 June 2008at9amI guess I’m to tired. I ment DLList but you have it already here.

Keep up the good work.

25 June 2008at9amAlso 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…

25 June 2008at9amI’ guess I’m posting in a wrong thread.

The fix is is for reverse function which is not recursive.

Sorry.

25 June 2008at9amNODEPTR 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..

30 July 2008at7pmreverse function returns struct node, but the reverse call made in the function does not return any value.

I doubt, if this would work.

18 September 2008at10amBy 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 😦

7 October 2008at2pmI 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.

7 October 2008at3pmThe 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;

}

24 October 2008at9pmtypedef 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);

}

}

2 November 2008at2am//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

27 November 2008at2amIn 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;

22 January 2009at11pmvoid 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

3 February 2009at12pmforgot to mention:

“head” is member of class linkedlist which

points to the head of the list when its created.

3 February 2009at12pmnode* 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;

10 June 2009at2pm