如何使用c ++在面向对象编程中使用递归来反转链表？

Question

我正在用c ++编写一个程序来反转c ++中的链表。我已经看到很多关于它的问题，但我的回答不是关于它们所以请不要将其标记为重复！

我想使用递归来反转链表，这是我的完整程序和函数反向递归（）这些程序结束并且不打印有问题。

我试图从我的班级中取出这个功能，但它不起作用，我也尝试使头部全局化。

class LinkedList{
public:
    Node* Head;
    int Length;
    LinkedList(Node* head,int c){
        Head=head;
        Length=c;
    }
    void ReverseRecursion(Node* temp,Node** Heading){
        if(temp->next==0){
            *Heading = temp;
            cout << "This is the head item==>" << temp->value << " And this 
            is the Heading now " << *Heading << endl;
            return;
        }
        ReverseRecursion(temp,Heading);
        temp->next->next = temp;
        temp->next = 0;
    }
}

我在这个类中插入，删除和打印功能但是我测试了它们并且它们是正确的。

在我的主要部分，我将head元素保存在main上的局部变量中，每次我将它传递给LinkedList。

我在main上调用这个函数：

MyLinked.ReverseRecursion(head,&head);

Answer 1

调用递归函数时，必须传递一个不同的参数，否则在内存不足之前会有无限递归。

试试这个版本，每次使用列表中的下一个元素调用该函数，直到找到列表的末尾：

class LinkedList{
public:
    Node* Head;
    int Length;
    LinkedList(Node* head,int c){
        Head=head;
        Length=c;
    }
    void ReverseRecursion(Node* temp,Node** Heading){
        if(temp->next==0){
            *Heading = temp;
            cout << "This is the head item==>" << temp->value << " And this 
            is the Heading now " << *Heading << endl;
            return;
        }
        ReverseRecursion(temp->next,Heading);
        temp->next->next = temp;
        temp->next = 0;
    }
}

编辑：

我展示了我的解决方案如何工作的完整测试。我打算对原始代码进行必要的最小更改以使其正常工作，并且最小值只更改一个单词：

#include <iostream>
using namespace std;

class Node {
  public:
    int value;
    Node * next;

    Node(int v, Node * n) : value(v), next(n) {}
};

class LinkedList{
public:
    Node* Head;
    int Length;
    LinkedList(Node* head,int c){
        Head=head;
        Length=c;
    }
    void ReverseRecursion(Node* temp,Node** Heading){
        if(temp->next==0){
            *Heading = temp;
            //cout << "This is the head item==>" << temp->value << " And this
            //is the Heading now " << *Heading << endl;
            return;
        }
        ReverseRecursion(temp->next,Heading);
        temp->next->next = temp;
        temp->next = 0;
    }
    void print() const;
};


void LinkedList::print() const {
  cout << '{';

  for (Node* node = Head; node != 0; node = node->next)
    cout << ' ' << node->value; // value is public ?

  cout << " }" << endl;
}


int main()
{
  Node n3(3, 0);
  Node n2(2, &n3);
  Node n1(1, &n2);
  LinkedList ll(&n1, 3);
  Node *heading;

  ll.print();
  ll.ReverseRecursion(&n1, &heading);
  ll.Head = heading;
  ll.print();

  return 0;
}

输出：

{ 1 2 3 }
{ 3 2 1 }