当我尝试使用递归反转链表时，代码陷入无限循环

Question

我试图使用递归反转链表，但是当我首先尝试打印出链表的所有元素时，它按预期打印出元素，但在打印出最后一个元素后，它开始打印最后一个和倒数第二个元素重复。我试图调试它，我认为问题是最后一个元素指向倒数第二个元素是否应该指向 NULL。我无法弄清楚我的代码有什么问题，所以请帮助我。

示例- 输入 1,2,3,4,5,6

预期输出 6,5,4,3,2,1

实际输出 6,5,4,3,2,1,2,1,2 ...

#include<iostream>
        
using namespace std;
class node{

public:
int val;
node *next;
node(int val)
{
  this->val = val;
  this->next = NULL; 
}
node(int val,node *next)
{
  this->val= val;
  this->next=next;
}

};

void insertAtTail(node *&head,int val){
  
  node *n = new node(val);
  if (head==NULL)
  {
    head = n;
    return;
  }
  node *temp = head;
  while (temp->next!=NULL)
  {
    temp = temp->next;
  }
  temp->next=n;

}
void display(node *head)
{
  node *n = head;
  while (n!=NULL)
  {
    cout << n->val << "->";
    n = n->next;
  }
  cout << "NULL" << endl;
  
}
node* reverseRecursive(node *&head)
{
  if (head == NULL || head->next==NULL)
  {
    return head;
  }
  node *nHead = reverseRecursive(head->next);
  head->next->next = head;
  head->next == NULL;
  return nHead; //  1->2->3->4->5->6->NULL  
}

int main()
{

node *head = NULL;
insertAtTail(head,1);
insertAtTail(head,2);
insertAtTail(head,3);
insertAtTail(head,4);
insertAtTail(head,5);
insertAtTail(head,6);
display(head);
node *newhead = reverseRecursive(head);
display(newhead);
return 0;
}

Answer 1

函数 reverseRecursive() 中存在错误。

行 head->next == NULL; 应该是 head->next = NULL;


node* reverseRecursive(node *&head)
{
  if (head == NULL || head->next==NULL)
  {
    return head;
  }
  node *nHead = reverseRecursive(head->next);
  head->next->next = head;
  head->next == NULL;                       // <<< should be  head->next = NULL;
  return nHead; //  1->2->3->4->5->6->NULL  
}

不确定您使用的是哪个编译器，但此语句通常会生成警告。

当我尝试使用递归反转链表时，代码陷入无限循环

code got strucked in a infinite loop when I tried to reverse a linked list using recursion

pointers

linked-list

infinite-loop