题目是力扣 206反转链表。输入单链表头节点反转指向关系返回新的头节点。例如 1 - 2 - 3 - null 变成 3 - 2 - 1 - null空链表仍是空链表。我最初的思路是把当前节点之后的链表交给递归后半段逆序完成后把当前节点接到它的末尾。“相信递归函数”很重要但还需要讲清两件事后半段的尾巴在哪里接回当前节点以后旧箭头怎么办1. 先约定函数的含义reverseList(head) 接收一条无环单链表的头节点把这条链表反转然后返回新头节点。它不是只反转一条边也不是返回原来的 head。因此调用 reverseList(head.next) 后可以按约定认为后半条已经反转返回值指向它的新头原来的第二个节点现在是这条后半链的尾节点。这张原图的红框是“交出去时”的后半段不是递归返回后的箭头方向。要理解接尾操作还要看下一步的状态。2. 用三个节点走到回溯这一刻原来是head | v 1 - 2 - 3 - null对节点 1 这一层先让递归处理 2 - 3。返回时后半段已经是 3 - 2 - null但是节点 1 的旧 next 还指向节点 2newHead | v 3 - 2 - null ^ | 1 - head于是 head.next 仍然是节点 2正好是反转后后半段的尾巴。我们可以改这个尾节点的 nexthead.next.next head; head.next null;第一句不是把 head.next 改成 head而是把“head.next 指向的那个节点”的 next 改成 head。时刻节点 1 的 next节点 2 的 next是否有环后半段递归返回后2null没有执行第一句后21暂时出现 1 与 2 的环执行第二句后null1没有得到 3 - 2 - 1这就是不能漏掉 head.next null 的原因。也不能直接把这两句交换先清空 head.next再执行 head.next.next会访问空引用。若要换顺序必须另存第二个节点的引用。原图用叉和红箭头叠在旧箭头上表示修改不代表结束后新旧箭头同时存在。读图时从最底层开始回溯最终应得到一条以 null 结尾的单链。3. 保留原来的递归实现平台已提供 ListNode 类型下面第一段按平台提交格式写。class Solution { public ListNode reverseList(ListNode head) { if (head null || head.next null) return head; ListNode newHead reverseList(head.next); head.next.next head; head.next null; return newHead; } }空链表和单节点不用改箭头。其余每层只完成“接回当前节点断开旧箭头”并把递归返回的新头继续传出去。所以不必从新头遍历寻找尾巴尾巴就是这一层的 head.next。如果每层再从头找尾会把原本线性的工作增加成平方级别。时间复杂度 O(n)递归栈空间 O(n)不是 O(1)。链表长时还受 Java 栈空间限制题目的节点范围不能保证每个运行环境都允许相同递归深度。4. 不想依赖调用栈可以迭代改箭头递归从后往前接迭代则从前往后逐条改边。开始时反转好的部分为空prev null尚未处理的部分从 cur 开始。class IterativeSolution { public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode next cur.next; cur.next prev; prev cur; cur next; } return prev; } }每轮动作为什么需要保存 next改边后仍能找到剩余链表cur.next prev当前节点接到已反转部分前面prev cur已反转部分的新头前进一步cur next继续处理原来的下一节点它同样是 O(n) 时间但只用固定数量的引用额外空间 O(1)。两种方法都重接原节点不需要新建一条数据相同的链表。5. 怎么证明测试不只是“打印顺序对了”只检查 3、2、1 太弱重新创建三个节点也能打印一样的结果两个相同值的节点交换错了也可能看不出来。本次用本地 Java 编译运行正文两段代码。测试器保留输入节点的引用列表检查输出是否按相反顺序返回这些原对象同时检查没有丢节点也没有多出节点。没有环最后一个节点的 next 为 null。节点值没有被悄悄交换。再反转一次恢复原来的节点顺序。覆盖空链表、单节点、重复值、负数和不同长度递归只测适中的长度长链另测迭代不把不同 JVM 的栈限制伪装成算法保证。我还故意删除递归中的 head.next null检查测试器能否抓到环删除迭代中的改边语句检查是否抓到节点遗漏。错误版本必须失败测试才不只是为正确代码背书。原来的“相信递归”现在可以再补一句先明确递归交还给我的状态再只处理当前这一层的两条链接。不懂时展开三节点懂了以后用函数约定理解长链而不是把每一层都画到纸上。