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
Data Structures Blog 
Nice recursive code for reversing the linked list!
since recursive calls uses stack the stack version for the same is mind blowing!
Really mind blowing implementation.The way the “node” and “node->next” pointers are used in this implementation is amazing.
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;
}
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.
I tried the piece of code by “ponnada” on a solaris platform just to see the result……
Segmentation Fault(coredump)
aftab
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
Why static??
i tried but it did not run
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.
I guess I’m to tired. I ment DLList but you have it already here.
Keep up the good work.
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…
I’ guess I’m posting in a wrong thread.
The fix is is for reverse function which is not recursive.
Sorry.
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..
reverse function returns struct node, but the reverse call made in the function does not return any value.
I doubt, if this would work.
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 😦
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.
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;
}
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);
}
}
//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
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;
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
forgot to mention:
“head” is member of class linkedlist which
points to the head of the list when its created.
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;