30
Mar
Reversing single linked list recursively
Related Blog Items
- Reversing a single linked list using stack
- Reversing a circular single linked list using pointers
- Reversing a double linked list
- Printing linked List in Reverse without Reversing The List Actually
- Reverse linked list using pointers
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.
struct Node *reverse(struct Node* node)
{
static struct Node *tmpnode = NULL;
static struct Node *headnode = NULL;
if (NULL == node)
{
return node;
}
if (node->next)
{
reverse(node->next);
tmpnode->next = node;
tmpnode = tmpnode->next;
}
else
{
headnode = node;
tmpnode = headnode;
}
tmpnode->next = NULL;
return headnode;
}
comments are always welcome…
Popularity: 91%
You need to log on to convert this article into PDF
Related Blog Items - Reversing a single linked list using stack
- Reversing a circular single linked list using pointers
- Reversing a double linked list
- Printing linked List in Reverse without Reversing The List Actually
- Reverse linked list using pointers
Related Blog Items
- Reversing a single linked list using stack
- Reversing a circular single linked list using pointers
- Reversing a double linked list
- Printing linked List in Reverse without Reversing The List Actually
- Reverse linked list using pointers
Nice recursive code for reversing the linked list!
since recursive calls uses stack the stack version for the same is mind blowing!
April 18th, 2007 at 2:09 pm
Really mind blowing implementation.The way the “node” and “node->next” pointers are used in this implementation is amazing.
May 30th, 2007 at 1:07 pm
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;
}
April 17th, 2008 at 2:07 pm
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.
April 17th, 2008 at 7:26 pm
I tried the piece of code by “ponnada” on a solaris platform just to see the result……
Segmentation Fault(coredump)
aftab
April 29th, 2008 at 2:35 pm
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
April 30th, 2008 at 10:15 am
Why static??
May 8th, 2008 at 12:44 pm
i tried but it did not run
June 5th, 2008 at 6:52 pm
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.
June 25th, 2008 at 9:22 am
I guess I’m to tired. I ment DLList but you have it already here.
Keep up the good work.
June 25th, 2008 at 9:31 am
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…
June 25th, 2008 at 9:37 am
I’ guess I’m posting in a wrong thread.
The fix is is for reverse function which is not recursive.
Sorry.
June 25th, 2008 at 9:42 am
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..
July 30th, 2008 at 7:40 pm