两两交换链表节点：相信递归之前，先看清这两次指针重连

这道题我最想记住的不是几行代码而是后面的链表交给递归当前这一层只负责两个节点和一次接链。但“相信递归”不能代替理解指针尤其是下面两句赋值的中间状态。1. 换的是节点不是节点的值力扣 24两两交换链表中的节点。相邻节点两两交换不能修改节点内部的值。空链表不变奇数长度的最后一个节点也不变。先给节点起名字。这里的 A、B、C、D 是节点身份不是存进去的值交换前A - B - C - D - null 交换后B - A - D - C - null若只是把 A.val 和 B.val 对调打印出来也可能一样但题目要求并没有完成。后面的测试因此会比较节点引用。2. 先约定递归函数能做什么swapPairs(head)接收一个链表头返回这个链表两两交换后的新头。它不是返回第二个节点也不是返回最后一个节点。当前有 A、B 两个节点时把 B 后面的链表交给递归得到新头 tmp。只要递归已经完成当前层要建立的结构就很明确递归输入C - D - ... 递归返回tmp - 已经交换好的后缀 当前目标B - A - tmp这张原图右边的方框代表递归处理后的整体不是说 3、4 在最终答案中仍保持原顺序。四节点的具体结果中tmp 指向节点 4。3. 我的原代码以及最容易跳过的中间状态class Solution { public ListNode swapPairs(ListNode head) { if (head null || head.next null) { return head; } ListNode tmp swapPairs(head.next.next); ListNode ret head.next; ret.next head; head.next tmp; return ret; } }这仍然是我原来的递归解法。平台提供 ListNode本地测试时另外定义这个类。执行位置当前层要记住什么递归返回后head 仍指向 Ahead.next 仍指向 Btmp 是已交换后缀的新头ret head.next用 ret 保存 B否则改链后不一定还能方便地找到它ret.next headB 指向 A此时 A 还指向 B暂时形成 A、B 两节点环head.next tmpA 改为指向后缀打断短暂的环形成 B - A - tmpreturn ret返回 B外层才知道这个局部链表的新入口短暂成环不是最终结果成环。在这两句之间不能插入链表遍历否则遍历可能停不下来。当前代码紧接着改写 head.next才完成重连。tmp 已经提前保存后缀不会因此丢失。也可以先保存第二个节点再先把 head 接到后缀、最后把第二个节点接到 head从而避免短暂成环。但不能不保存引用就机械交换原来两行先修改 head.next随后再读取它拿到的已经不是原来的 B。4. 手动展开一次再回到局部推理以四节点为例内层从 C 开始继续调用空链表返回 null内层连接 D - C - null 并返回 D。外层得到 tmp D接成 B - A - D - C - null。空链表或只有一个节点时直接返回是这套约定的起点。若后缀能正确交换当前层又能把前两个节点接成 B - A - 后缀那么整个链表就正确。奇数长度最后的独立节点通过这个出口自然保留下来不必单独补一次交换。时间复杂度 O(n)。但递归每层只跳过两个节点调用栈仍是 O(n)不是 O(1) 额外空间。如果链表非常长应考虑迭代写法不能指望 Java 自动消除这种递归的栈开销。5. 不只看输出验证节点身份、数量和值下面保存为 SwapPairsCheck.java把前面的 Solution 放到同目录 Solution.java。它直接调用上面的算法不另写一个“看起来一样”的版本来代测。class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } } public class SwapPairsCheck { public static void main(String[] args) { int cases 0; for (int n 0; n 100; n) { for (int mode 0; mode 2; mode) { ListNode[] nodes new ListNode[n]; for (int i 0; i n; i) { nodes[i] new ListNode(mode 0 ? i : 7); if (i 0) nodes[i - 1].next nodes[i]; } ListNode p new Solution().swapPairs(n 0 ? null : nodes[0]); for (int pos 0; pos n; pos) { int expected pos % 2 0 ? (pos 1 n ? pos 1 : pos) : pos - 1; if (p ! nodes[expected]) { throw new AssertionError(identity: n n , pos pos); } if (p.val ! (mode 0 ? expected : 7)) { throw new AssertionError(node value changed); } p p.next; } if (p ! null) throw new AssertionError(extra node or cycle); cases; } } System.out.println(PASS: cases identity/value/termination cases); } }javac Solution.java SwapPairsCheck.java java SwapPairsCheck本次使用 Java 17 在临时目录编译运行结果PASS: 202 identity/value/termination cases0100 的所有长度各测试两种值递增值与完全相同的值。重复值尤其重要如果只打印数字七和七交换后根本看不出节点是否移动。这里逐个核对原节点引用再检查每个值没被改、最后确实终止能发现只换值、丢节点、重复节点和结果成环等错误。这些是本地构造案例不是重新提交力扣隐藏测试也没有穷举所有指针输入图输入前提仍是正常的无环单链表。本次还故意试了“只换值”和“漏接后缀”的错误版本验证程序都能拒绝。历史的 0 ms 截图不意味着算法没有耗时也不值得据此断言最快。真正可解释的是 O(n) 的遍历和 O(n) 的递归栈。最后还是保留我原来的提醒不理解时手动展开一次理解后把注意力收回当前层的输入、返回值和指针连接。相信递归函数前提是先讲清楚它承诺做什么。