反向链表（递归）真的服啦（相关搜索：单链表）

Question

代码问题：给定一个头节点为 head 的单链表用于记录一系列核心肌群训练编号，请将该系列训练编号 倒序 记录于链表并返回。
代码逻辑：通过递归的特性（结束后逐步返回）来实现反向链接
我的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* head_end;//最后的head头指针
    ListNode* tmpptr;//迭代指针

    bool pass(ListNode*& curptr) {
        if (curptr != NULL && curptr->next != NULL) {//递归的依据是有没有到头
            if (!pass(curptr->next)) {
                return false;
            }
            tmpptr->next = curptr;
            curptr->next = NULL;//为什么这一行删掉就出问题了
            tmpptr = tmpptr->next;
            return true;
        } else {
            head_end = curptr;
            tmpptr = curptr;
            return true;
        }
    }
    ListNode* trainningPlan(ListNode* head) {
        pass(head);
        return head_end;
    }
};

我的问题：
上述代码注释行curptr->next = NULL;为什么删掉就有问题了（报错显示：这表示你在尝试访问一块已经被释放的内存）？tmpptr->next = curptr;这句代码不是已经实现了对上一层递归中（按照返回的先后顺序）的curptr进行了重新链接了吗？

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

这个问题的关键在于理解递归的工作原理以及如何正确地操作链表结构。在删除curptr->next = NULL;这一行后，会出现问题，是因为在递归过程中，你没有正确地处理链表的节点连接。具体来说，你的代码逻辑在递归过程中改变了链表的连接结构，但没有正确地处理返回时的链接重建。

在递归函数中，当你深入递归时，你正在遍历链表的节点并尝试改变它们的连接。然而，当你从递归返回时，你需要确保已经遍历过的节点能够以正确的顺序重新连接起来。在你的代码中，tmpptr->next = curptr;这行代码的目的是在递归返回时重新连接节点。然而，由于你没有设置curptr->next = NULL;，原先指向curptr的下一个节点的指针并未被改变或清空，这就导致你在试图操作已经不属于当前节点的内存空间，从而出现错误。同时这也可能破坏了原先链表的完整性，造成无法预测的行为。因此当删掉那一行代码后就会报错，因为访问了一块已经被释放的内存空间。实际上那个空间还在被原来链表的下一个节点引用，但是因为某种原因那个引用失效了。当重新组织链表时由于没有清除这些已经失效的引用导致出现错误。总的来说这是一种非常典型的由于不正确修改数据结构引起的错误类型。要正确地修复这个问题，必须正确地设置节点间的链接以保证数据结构在遍历过程中不被破坏并且保持正确的连接关系。所以保留curptr->next = NULL;这一行是必要的。同时也要注意处理好边界条件以及递归的终止条件以确保代码的正确性。