What is wrong with this way to reverse a linked list recursively?

Question

I am trying to reverse a linked list using recursion, but somehow it's not working. I know something I am doing is obviously wrong, but I would really appreciate any advice.

Here's my code:

#include <iostream>

using namespace std;

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

typedef Node* nodePtr;

void reverseList(nodePtr &list) {
    nodePtr temp = list;
    if (temp->next == nullptr) {
        list = temp;
        return;
    }
    else {
        reverseList(temp->next);
        nodePtr temp2 = temp->next;
        temp2->next = temp;
        temp->next = nullptr;
    }
}

void insertEnd(nodePtr &list, int data) {
    nodePtr temp = new Node;
    temp->data = data;
    temp->next = nullptr;
    if (list == nullptr) {
        list = temp;
    }
    else {
        nodePtr temp2 = list;
        while(temp2->next != nullptr) {
            temp2 = temp2->next;
        }
        temp2->next = temp;
    }
}

void printList(nodePtr list) {
    nodePtr temp = list;
    cout << "The list is: " << endl;
    while (temp != nullptr) {
        cout << temp->data << endl;
        temp = temp->next;
    }
}

int main() {
    nodePtr head = new Node;
    head = nullptr;
    insertEnd(head, 1);
    insertEnd(head, 2);
    insertEnd(head, 3);
    insertEnd(head, 4);
    insertEnd(head, 5);
    insertEnd(head, 6);
    printList(head);
    reverseList(head);
    printList(head);
}

The insertEnd() and printList() functions work correctly, as every time I run it, it prints:

1
2
3
4
5
6

However, when I invoke the reverseList() function and try to print that, it only prints:

1

Answer 1

Basically, your else clause in the body of reverseList is just not doing the right thing. You pop the head, recursively reverse the list with the head removed, and then need to add the old head to the tail of the result of the recursive call.

Your code never deals with the fact that when you reverse part of the list you need the tail of what you reversed -- there is no getting around that. So you could either find that tail with a function that traverses a list and returns the last element, or you could return it in some way from your recursive call.

Below I do the latter, by taking an optional pointer to pointer that will fill the tail if the argument is not null.

#include <iostream>

using namespace std;

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

typedef Node* nodePtr;

void printList(nodePtr list) {
    nodePtr temp = list;
    cout << "The list is: " << endl;
    while (temp != nullptr) {
        cout << temp->data << endl;
        temp = temp->next;
    }
}

void reverseList(nodePtr& list, nodePtr* tail = nullptr) {
    if (list->next == nullptr) {
        if (tail) {
            *tail = list;
        }
    } else {
        auto reversed = list->next;
        nodePtr tail_of_reversed = nullptr;
        reverseList(reversed, &tail_of_reversed);

        auto old_head = list;
        old_head->next = nullptr;
        tail_of_reversed->next = old_head;

        if (tail) {
            *tail = old_head;
        }
        list = reversed;
    }
}

void insertEnd(nodePtr& list, int data) {
    nodePtr temp = new Node;
    temp->data = data;
    temp->next = nullptr;
    if (list == nullptr) {
        list = temp;
    }
    else {
        nodePtr temp2 = list;
        while (temp2->next != nullptr) {
            temp2 = temp2->next;
        }
        temp2->next = temp;
    }
}


int main() {
    nodePtr head = new Node;
    head = nullptr;
    insertEnd(head, 1);
    insertEnd(head, 2);
    insertEnd(head, 3);
    insertEnd(head, 4);
    insertEnd(head, 5);
    insertEnd(head, 6);
    printList(head);
    reverseList(head);
    printList(head);
}