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.
Related posts:
Node * reverse(Node * cur) {
if(cur->next==NULL) return cur;
Node *tmp = rreverse(cur->next);
cur->next->next = cur;
return tmp;
}
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.
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.
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;
}
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;
}
}
Thanks Aswin, this is the best solution I have seen for this topic.
This very question was on Microsoft interview.
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).
@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
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.
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);
}
}
Hey Matt, thanks for pointing it out. Now I know not to write posts at 2am…
Updated the code.
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.