1. 题目背景与核心需求合并两个有序链表是算法面试中的经典问题在LeetCode题库中被标记为简单难度题号21。这道题考察的是对链表基本操作的掌握程度以及双指针和递归两种解法的灵活运用能力。在实际开发中合并有序链表的场景非常常见。比如合并两个按时间排序的日志流归并排序算法中的子问题数据库查询结果的合并操作题目给出的链表节点定义如下Java版本public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }2. 双指针解法详解2.1 算法思路解析双指针解法是这类问题的标准解法时间复杂度O(nm)空间复杂度O(1)。核心思想是创建一个虚拟头节点(dummy)作为结果链表的起点使用两个指针分别遍历两个链表比较当前两个节点的值将较小的节点连接到结果链表移动对应链表的指针到下一个节点重复上述过程直到某个链表遍历完成将剩余未遍历完的链表直接连接到结果链表末尾2.2 Java实现代码public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy new ListNode(-1); // 虚拟头节点 ListNode current dummy; while (list1 ! null list2 ! null) { if (list1.val list2.val) { current.next list1; list1 list1.next; } else { current.next list2; list2 list2.next; } current current.next; } // 连接剩余部分 current.next (list1 ! null) ? list1 : list2; return dummy.next; }2.3 关键点与注意事项虚拟头节点的使用简化了边界条件处理while循环的条件是list1 ! null list2 ! null确保两个链表都还有节点时才比较最后需要处理剩余节点直接连接即可不需要再逐个遍历时间复杂度分析最坏情况下需要遍历两个链表的所有节点所以是O(nm)空间复杂度只使用了常数级别的额外空间(O(1))注意在实际面试中建议先画出链表操作的示意图帮助理清指针移动的逻辑。3. 递归解法深入剖析3.1 递归思路解析递归解法的时间复杂度同样是O(nm)但空间复杂度是O(nm)递归调用栈的开销。核心思想是定义递归终止条件当某个链表为空时直接返回另一个链表比较两个链表当前节点的值选择较小的节点作为当前节点对该节点的next指针递归调用合并函数返回当前节点3.2 Java递归实现public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1 null) return list2; if (list2 null) return list1; if (list1.val list2.val) { list1.next mergeTwoLists(list1.next, list2); return list1; } else { list2.next mergeTwoLists(list1, list2.next); return list2; } }3.3 递归解法的优缺点优点代码简洁逻辑清晰不需要额外创建虚拟头节点天然符合分治思想缺点递归调用栈可能造成栈溢出对于极长的链表空间复杂度较高调试相对困难提示在面试中通常建议先给出双指针解法然后可以提到这个问题也可以用递归解决如果面试官要求再实现递归版本。4. 边界条件与异常处理4.1 常见边界情况两个链表都为空其中一个链表为空链表中有重复元素链表长度差异很大一个很长一个很短4.2 测试用例设计// 测试用例示例 Test public void testMergeTwoLists() { // 两个空链表 assertNull(mergeTwoLists(null, null)); // 一个空链表 ListNode list1 new ListNode(1); assertEquals(list1, mergeTwoLists(list1, null)); // 常规情况 ListNode list2 new ListNode(2); ListNode merged mergeTwoLists(list1, list2); assertEquals(1, merged.val); assertEquals(2, merged.next.val); // 包含重复元素 ListNode list3 new ListNode(1, new ListNode(3)); ListNode list4 new ListNode(2, new ListNode(3)); merged mergeTwoLists(list3, list4); assertEquals(1, merged.val); assertEquals(2, merged.next.val); assertEquals(3, merged.next.next.val); assertEquals(3, merged.next.next.next.val); }5. 算法优化与变种问题5.1 迭代解法优化可以通过消除虚拟头节点来稍微优化空间使用public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1 null) return list2; if (list2 null) return list1; ListNode head, current; if (list1.val list2.val) { head current list1; list1 list1.next; } else { head current list2; list2 list2.next; } while (list1 ! null list2 ! null) { if (list1.val list2.val) { current.next list1; list1 list1.next; } else { current.next list2; list2 list2.next; } current current.next; } current.next (list1 ! null) ? list1 : list2; return head; }5.2 相关变种问题合并K个有序链表LeetCode 23合并两个有序数组LeetCode 88合并两个链表到特定位置LeetCode 16695.3 实际工程中的应用在数据库系统中合并有序链表常用于多路归并排序索引合并查询结果合并在大数据处理中MapReduce框架的shuffle阶段也涉及类似操作。6. 个人解题心得与技巧画图辅助理解在纸上画出链表和指针的变化过程能极大帮助理解先处理边界条件先考虑空链表的情况避免后续处理中出现NPE双指针法优先在面试中通常更倾向于看到双指针解法递归解法作为备选虽然代码简洁但要清楚说明其空间复杂度问题测试用例设计特别注意边界条件和极端情况的测试变量命名清晰使用list1/list2比l1/l2更易读current比prev/next更明确在实际编码中我发现很多同学容易犯的错误包括忘记移动current指针循环条件写错比如写成||而不是最后剩余部分处理不当没有正确处理空链表的情况经验分享在链表问题中虚拟头节点(dummy node)是一个非常有用的技巧可以简化很多边界条件的处理。这个技巧在删除链表节点、反转链表等问题中同样适用。