CODEWITHSUNDEEP
c++linked-list
Sakshi Tanwar
Sakshi Tanwar

Reputation: 53

Reversing LinkedList result in wrong links by recursion

I wrote the following code to reverse a linked list recursively for my homework. However, It's not connecting the links properly. Can please someone tell me what's wrong in the following reverse function? I have tried GDB as well. But, could not figure out what's wrong?

#include <iostream>
using namespace std;

class Node
{
public:
    int data;
    Node *next;
    explicit Node(int data)
    {
        this->data = data;
        next = nullptr;
    }
};

void pushBack(Node * &head, Node * &tail, int data)
{
    if(head == nullptr)
    {
        head = new Node(data);
        tail = head;
    }

    else
    {
        tail->next = new Node(data);
        tail = tail->next;
    }
}

void printList(Node *head)
{
    if(head == nullptr)
        return;
    cout << head->data << " ";
    printList(head->next);
}


void reverseListRecursive(Node * &head)
{
    if(head->next == nullptr)
    {
        return;
    }

    reverseListRecursive(head->next);

    head->next->next = head;
    head->next = nullptr;
}

int main()
{
    int cap;
    cin >> cap;
    Node *head = nullptr, *tail = nullptr;
    for(int i = 0; i < cap; ++i)
    {
        int element;
        cin >> element;
        pushBack(head, tail, element);
    }

    reverseListRecursive(head);
    printList(head);
    return 0;
}

Head is being passed by reference and also the infinite recursion is also not there.

Upvotes: 0

Views: 48

Answers (1)

Sakshi Tanwar
Sakshi Tanwar

Reputation: 53

The problem is that the head pointer needs to point to the last node of the linked list. Following code fixes the problem.

void reverseListRecursive(Node * &head, Node *temp = nullptr)
{
    if(temp == nullptr)
        temp = head;

    if(temp->next == nullptr)
    {
        head = temp;
        return;
    }

    reverseListRecursive(head, temp->next);

    temp->next->next = temp;
    temp->next = nullptr;

}

Upvotes: 1

Related Questions