I am trying to just write a basic function that reverses a singly-linked list which is recursive. I was wondering if i tackled this in the right approach? Maybe someone can give me some pointers.
void reverse(Node*& p) {
if (!p) return;
Node* rest = p->next;
if (!rest) return;
reverse(rest);
p->next->next = p;
p->next = NULL;
p = rest;
}
That's not the most efficient way, but to do it, you can call the reverse method with the "next" pointer until there is no next. Once there, set next to previous. After returning from the recursion, set next to previous. See the recursive version here for an example. From the link:
Node * reverse( Node * ptr , Node * previous)
{
Node * temp;
if(ptr->next == NULL) {
ptr->next = previous;
previous->next = NULL;
return ptr;
} else {
temp = reverse(ptr->next, ptr);
ptr->next = previous;
return temp;
}
}
reversedHead = reverse(head, NULL);
This might be helpful
List
{
public:
.....
void plzReverse()
{
Node* node = myReverse(head);
node->next = NULL;
}
private:
Node * myReverse(Node * node)
{
if(node->next == NULL)
{
head = node;
return node;
}
else
{
Node * temp = myReverse(node->next);
temp ->next = node;
return node;
}
}
}
Another solution might be:
List
{
public:
.....
void plzReverse()
{
Node* node = myReverse(head, head);
node->next = NULL;
}
private:
Node * myReverse(Node * node, Node*& rhead)
{
if(node->next == NULL)
{
rhead = node;
return node;
}
else
{
Node * temp = myReverse(node->next,rhead);
temp ->next = node;
return node;
}
}
}
This is what you need:
Node* reverse(Node* p) {
if (p->next == NULL) {
return p;
} else {
Node* t = reverse(p->next); // Now p->next is reversed, t is the new head.
p->next->next = p; // p->next is the current tail, so p becomes the new tail.
p->next = NULL;
return t;
}
}
The recursive solution can look quite pretty, even in C++:
Node* reverse(Node* pivot, Node* backward = 0) {
if (pivot == 0) // We're done
return backward;
// flip the head of pivot from forward to backward
Node* rest = pivot->next;
pivot->next = backward;
// and continue
return reverse(rest, pivot);
}
Most C++ compilers do tail call optimization so there's no reason to believe this to be less efficient than an iterative solution.
Here is the solution that preserves return value as void.
void reverse(Node*& p) {
if (!p) return;
Node* rest = p->next;
if (!rest) {
rest = p;
return;
}
reverse(rest);
p->next->next = p;
p->next = NULL;
p = rest;
}
linkedList *reverseMyNextPointer(linkedList *prevNode, linkedList *currNode)
{
linkedList *tempPtr;
if(!currNode)
return prevNode;
else
{
tempPtr = currNode->next;
currNode->next = prevNode;
return reverseMyNext(currNode,tempPtr);
}
}
head = reverseMyNextPointer(nullptr,head);
