Reversing a linked list starting from the tail using recursion

Question

I still struggle with the recursion technique to solve the problem. I know there are nicer ways to solve my problem below of reversing a linked list. Most of the ways that I have seen, start to reverse the pointers by going from the head to the tail, either by using iteration or recursion.

I am trying for interest to reverse the list by first finding the last node in the list recursively and then changing the pointers everytime the function returns.

What am I doing wrong below exactly? Or will this method even work , without the need to pass more parameters to the recursive function? Thanks in advance for your help.

struct Node
{
    int data;
    struct Node *next;
};

Node* Reverse(Node *head)
{
    static Node* firstNode = head;
    // if no list return head
    if (head == NULL)
    {
        return head;
    }

    Node* prev = NULL;
    Node* cur = head;

    // reached last node in the list, return head
    if (cur->next == NULL)
    {
        head = cur;
        return head;
    }

    prev = cur;
    cur = cur->next;
    Reverse(cur)->next = prev;

    if (cur == firstNode)
    {
        cur->next = NULL;
        return head;
    }
    return cur;
}

EDIT : Another attempt

Node* ReverseFromTail(Node* prev, Node* cur, Node** head);

Node* ReverseInit(Node** head)
{
    Node* newHead = ReverseFromTail(*head, *head, head);
    return newHead;
}



Node* ReverseFromTail(Node* prev, Node* cur, Node** head)
{
    static int counter = 0;
    counter++;

    // If not a valid list, return head
    if (head == NULL)
    {
        return *head;
    }

    // Reached end of list, start reversing pointers
    if (cur->next == NULL)
    {
        *head = cur;
        return cur;
    }


    Node* retNode = ReverseFromTail(cur, cur->next, head);
    retNode->next = cur;


    // Just to force termination of recursion when it should. Not a permanent solution 
    if (counter == 3)
    {
        cur->next = NULL;
        return *head;
    }

    return retNode;
}

Finally Solved it :

Node* NewestReverseInit(Node* head)
{
    // Invalid List, return
    if (!head)
    {
        return head;
    }

    Node* headNode = NewestReverse(head, head, &head);

    return headNode;
}

Node* NewestReverse(Node *cur, Node* prev, Node** head)
{
    // reached last node in the list, set new head and return
    if (cur->next == NULL)
    {
        *head = cur;
        return cur;
    }

    NewestReverse(cur->next, cur, head)->next = cur;

    // Returned to the first node where cur = prev from initial call
    if (cur == prev)
    {
        cur->next = NULL;
        return *head;
    }

    return cur;
}

Answer 1

It can be done. The key in understanding recursion is What is the starting point?

Usually I create a "starting" function which prepares the first call. Sometimes it is a separate function (like in non OO implemnatation at bottom). Sometimes it's just a special first call (like in example below).

Also the key is in remembering variables before they change and what is the new head.

The new head is the last element of the list. So You have to get it up from the bottom of the list.

The nextelement is always your parent.

Then the trick is to do everything in the correct order.

    Node* Reverse( Node* parent) // Member function of Node.
    {
        Node* new_head = next ? next->Reverse( this ) 
                              : this;

        next = parent;

        return new_head;
    }

You call the function with: var.Reverse( nullptr);

Example:

int main()
{
    Node d{ 4, nullptr };
    Node c{ 3, &d };
    Node b{ 2, &c };
    Node a{ 1, &b };

    Node* reversed = a.Reverse( nullptr );
}

So what is happening here?

First we create a linked list:

 a->b->c->d->nullptr

Then the function calls:

1. a.Reverse(nullptr) is called.
2. This calls the Reverse on the next node b.Reverse with parent a.
3. This calls the Reverse on the next node c.Reverse with parent b.
4. This calls the Reverse on the next node d.Reverse with parent c.
5. d doesn't have next node so it says that the new head is itself.
6. d's next is now it's parent c
7. d returns itself as the new_head.
8. Back to c: new_head returned from d is d
9. c's next is now it's parent b
10. c returns the new_head it recieved from d
11. Back to b: new_head returned from c is d
12. b's next is now it's parent a
13. b returns the new_head it recieved from c
14. Back to a: new_head returned from b is d
15. a's next is now it's parent nullptr
16. a returns the new_head it recieved from b
17. d is returned

---

Non object oriented implementation;

Node* reverse_impl(Node* parent)
{
    Node* curr = parent->next;
    Node* next = curr->next;

    Node* new_head = next ? reverse_impl( curr ) 
                          : curr;

    curr->next = parent;

    return new_head;
}

Node* reverse(Node* start)
{
    if ( !start )
        return nullptr;

    Node* new_head = reverse_impl( start );
    start->next    = nullptr;

    return new_head;
}

Answer 2

Here's a full implementation I wrote in 5 minutes:

#include <stdio.h>

struct Node
{
     int data;
     struct Node *next;
};

struct Node* Reverse(struct Node *n)
{
    static struct Node *first = NULL;

    if(first == NULL)
      first = n;

    // reached last node in the list
    if (n->next == NULL)
      return n;

    Reverse(n->next)->next = n;

    if(n == first)
    {
      n->next = NULL;
      first = NULL;     
    }

    return n;
}

void linked_list_walk(struct Node* n)
{
  printf("%d", n->data);
  if(n->next)
    linked_list_walk(n->next);
  else
    printf("\n");
}

int main()
{
  struct Node n[10];
  int i;

  for(i=0;i<10;i++)
  {
    n[i].data = i;
    n[i].next = n + i + 1;
  }
  n[9].next = NULL;

  linked_list_walk(n);
  Reverse(n);
  linked_list_walk(n+9);
}

Output:

0123456789                                                                                                                                                                          
9876543210 

Answer 3

I will not give you the code, I will give you the idea. You can implement the idea in the code.

The key to all recursion problems is to figure out two cases: repetition step and end case. Once you do this, it works almost as if magically.

Applying this principle to reversing a linked list:

• End case: the list of one element is already reversed (this is straightforward) and returning the element itself
• Repetition case: Given list L, reversing this least means reversing an L', where L' is the L' is the list without the very first element (usually called head), and than adding the head as the last element of the list. Return value would be the same as a return value of the recursive call you just made.