我原来的解法抓住了一件事选出当前较小的头节点剩下两个链表交给递归。但读懂代码还要回答一个问题递归得到的链表已经有序为什么仍然必须把它接到当前节点的 next 上1. 题意拼接已有节点不是重新抄一份值力扣 21合并两个有序链表。两个输入按非递减顺序排列合并结果由给定链表的节点组成。允许重复值一个输入为空时返回另一个即可。本文输入前提是两条正常、无环、互不共享节点的单链表。共享后缀是另一个输入模型不能直接把这段原地接链程序当作通用解法。给第一条节点命名 A1、A2、A3第二条命名 B1、B2、B3。同值也不是同一个节点AA1(1) - A2(2) - A3(4) BB1(1) - B2(3) - B3(4) 使用 时A1 - B1 - A2 - B2 - A3 - B32. 相信递归但先约定它返回什么mergeTwoLists(l1, l2)返回两条剩余链表合并后的头节点不是把答案藏在某个全局变量中。假设 l1 的头更小那么它应成为当前答案的头把l1.next和 l2 合并后答案要变成当前较小节点 l1 - 递归返回的有序后缀注意原图的颜色顺序有一处不严谨图中同值的紫色 1 排在红色 1 前但下面的实际先取第一条链表的红色 1。题目只看数值两种结果都合法若讨论节点身份和跨链表同值的先后顺序应以上面的节点序列和代码为准。保留原图是为了保留局部思考过程不把颜色顺序当作精确执行记录。3. 原来的 Java 解法class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 null) return l2; if (l2 null) return l1; if (l1.val l2.val) { l1.next mergeTwoLists(l1.next, l2); return l1; } else { l2.next mergeTwoLists(l1, l2.next); return l2; } } }这里有三个不同动作比较决定谁当头递归处理剩余部分赋值将当前头接上后缀。缺少最后这个赋值递归调用就算完成也没有把当前层连进正确的结果。l1.next mergeTwoLists(l1.next, l2)的右侧调用先完成结果才被赋给左侧。调用参数使用的是原来的 l1.next赋值之后它才变成合并后缀的新头。出口也不需要把另一条链表继续拆开一条已经为空另一条本来就有序原样接上剩余整段即可。输入节点的 next 会被改写调用后不要再把原输入头当作两条独立链表使用。4. 手动展开一次真正要理解的是回接代码按 A1、B1、A2、B2、A3 的顺序选择当前头然后第一条为空直接返回 B3。递归回退时依次接上 A3、B2、A2、B1、A1。为什么较小头可以放心留下因为两个输入都有序当前所有剩余元素都不小于它。如果后缀合并正确前面接上这个最小节点仍然有序。这个局部论证比“递归神奇地完成了”更具体。设长度为 n、m最坏时间 O(nm)调用栈最坏也为 O(nm)。没有新建结果节点不代表没有额外空间。大链表可以改迭代使用尾指针逐个接链避免深递归。5. 验证不要只盯着数字下面的测试把值合并排序作为参考但还核对原节点对象没有新建结果节点、没有重复出现原节点、没有改值、没有成环。保存为 MergeCheck.java与上面的 Solution.java 一起编译。import java.util.*; class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } } public class MergeCheck { static ListNode build(int[] values, MapListNode, Integer original) { ListNode head null, tail null; for (int value : values) { ListNode node new ListNode(value); original.put(node, value); if (head null) head node; else tail.next node; tail node; } return head; } static void check(int[] a, int[] b) { MapListNode, Integer original new IdentityHashMap(); ListNode left build(a, original), right build(b, original); int[] expected new int[a.length b.length]; System.arraycopy(a, 0, expected, 0, a.length); System.arraycopy(b, 0, expected, a.length, b.length); Arrays.sort(expected); SetListNode seen Collections.newSetFromMap(new IdentityHashMap()); ListNode p new Solution().mergeTwoLists(left, right); for (int value : expected) { if (p null || !original.containsKey(p) || !seen.add(p)) { throw new AssertionError(lost/copied/repeated node); } if (p.val ! value || p.val ! original.get(p)) { throw new AssertionError(wrong order or changed value); } p p.next; } if (p ! null) throw new AssertionError(extra node or cycle); } public static void main(String[] args) { int[][] fixtures {{}, {0}, {1, 1}, {-100, 0, 100}, {1, 2, 4}, {1, 3, 4}}; int cases 0; for (int[] a : fixtures) for (int[] b : fixtures) { check(a, b); cases; } Random random new Random(20261004L); for (int t 0; t 1000; t) { int[] a random.ints(random.nextInt(51), -100, 101).sorted().toArray(); int[] b random.ints(random.nextInt(51), -100, 101).sorted().toArray(); check(a, b); cases; } ListNode a new ListNode(7), b new ListNode(7); ListNode result new Solution().mergeTwoLists(a, b); if (result ! a || result.next ! b || b.next ! null) { throw new AssertionError( tie policy changed); } System.out.println(PASS: cases merge cases tie identity check); } }javac Solution.java MergeCheck.java java MergeCheckJava 17 本次实际输出PASS: 1036 merge cases tie identity check固定种子方便复现不等于随机测试是完备证明。参考值用数组排序得到不复制待测的接链逻辑对象集合专门检查“拼接原节点”的约束。最后的同值身份测试用于核对本文的约定换成也能满足力扣的值序列要求但不满足这个额外约定。验证器还拒绝了“漏掉 next 回接”和“复制一份新节点输出”的错误版本。本次没有重新提交力扣。和两两交换链表对照两题都接收递归返回的后缀头但当前层的接链目标不同。合并是“最小节点 - 合并后缀”交换是“第二节点 - 第一节点 - 交换后缀”。先画出这一层想得到的结构再写 next才更不容易丢节点。