在数据结构与算法的学习路径上，链表操作是构建编程思维的重要基石。LeetCode第21题“合并两个有序链表”以其清晰的问题定义和典型的解题模式，成为每位开发者必须掌握的经典。LeetCode 021 合并两个有序链表的核心价值在于，它不仅是检验你链表操作熟练度的试金石，更是理解递归思想、掌握双指针（或迭代）技巧、以及为后续解决“合并K个排序链表”等复杂问题铺平道路的关键一步。成功解决此题，意味着你能够驾驭链表节点的动态连接，并能在“自顶向下”的递归分解与“自底向上”的迭代构建两种思维模式间自由切换。
一、问题理解：何为“有序合并”
题目要求将两个按非递减顺序排列的链表合并为一个新的有序链表。新链表应该通过拼接给定的两个链表的所有节点组成。
关键点与约束： - **输入**：两个链表的头节点 `l1` 和 `l2`。 - **输出**：一个新链表的头节点，其节点值来自 `l1` 和 `l2`，且整体有序。 - **核心操作**：比较两个链表当前节点的值，将较小者接入新链表，并移动对应链表的指针。 - **原地与否**：通常我们创建一个新的哨兵节点（dummy node）来简化连接逻辑，但节点本身是复用原有的，并非创建全新节点。
示例： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
直观理解，这个过程类似于合并两叠已经排好序的卡片，你总是比较两叠最上面的那张，取出较小（或相等）的一张放入新叠，直到某一叠或两叠取完。
二、迭代解法（双指针）：步步为营的构建艺术
迭代解法是符合直觉、效率优异且易于理解的方案。其核心是使用一个哨兵节点（Dummy Node） 和 一个当前指针（Current Pointer）。
算法步骤详解：
1. **创建哨兵节点**：`ListNode dummy = new ListNode(-1);`。这是一个辅助节点，它的 `next` 将最终指向合并后链表的真实头节点。使用哨兵节点的巨大优势在于，它免去了对合并后链表头节点初始化的特殊判断（即不知道头节点是来自l1还是l2），让连接逻辑始终保持一致。
2. **初始化当前指针**：`ListNode curr = dummy;`。`curr` 始终指向新链表的最后一个节点，方便后续连接。
3. **循环比较与连接**：当 `l1` 和 `l2` 都不为空时： - 比较 `l1.val` 和 `l2.val`。 - 将 `curr.next` 指向值较小的那个节点。 - 移动被选中链表（如 `l1`）的指针到其下一个节点：`l1 = l1.next`。 - 移动 `curr` 指针到新链表的最新末尾：`curr = curr.next`。
4. **处理剩余部分**：循环结束后，`l1` 和 `l2` 中至少有一个为空。由于原链表有序，直接将 `curr.next` 指向那个非空的链表即可。
5. **返回结果**：返回 `dummy.next`，即真正的新链表头节点。
代码实现：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 创建哨兵节点
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
// 双指针遍历两个链表
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
// 连接剩余的链表部分
curr.next = (l1 != null) ? l1 : l2;
return dummy.next; // 哨兵节点的下一个就是新头节点
}
复杂度分析： - **时间复杂度 O(n + m)**：其中 n 和 m 分别是两个链表的长度。每个节点恰好被访问一次。 - **空间复杂度 O(1)**：我们只使用了固定的几个指针变量（`dummy`, `curr`），是常数级别的额外空间。尽管创建了一个 `dummy` 节点，但题目通常不将其计入空间复杂度，或者认为是 O(1)。
三、递归解法：优雅的分治自归并
递归解法体现了“分而治之”的思想，代码极其简洁，是理解递归在链表操作中应用的绝佳范例。其核心思路是：定义递归函数的意义，并找出问题规模缩小的方式。
递归定义： `mergeTwoLists(l1, l2)` 函数返回的是合并 `l1` 和 `l2` 后链表的头节点。
算法逻辑： 1. **基准条件（递归出口）**：如果 `l1` 为空，说明 `l1` 链表已全部合并，直接返回 `l2`；反之，如果 `l2` 为空，则返回 `l1`。
2. **递归体（规模减小）**： - 比较 `l1.val` 和 `l2.val`。 - 如果 `l1.val` 更小，那么 `l1` 应该是新链表的头节点。接下来，我们需要合并 `l1.next` 和 `l2` 这两个链表，并将合并结果接在 `l1` 后面。即：`l1.next = mergeTwoLists(l1.next, l2);` 然后返回 `l1`。 - 同理，如果 `l2.val` 更小或相等，则 `l2.next = mergeTwoLists(l1, l2.next);` 并返回 `l2`。
代码实现：
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=[1,2,4], l2=[1,3,4] 为例）：
第一层：l1.val(1) <= l2.val(1) -> l1(1).next = merge(l1(2,4), l2(1,3,4))
第二层：l2.val(1) < l1.val(2) -> l2(1).next = merge(l1(2,4), l2(3,4))
第三层：l1.val(2) < l2.val(3) -> l1(2).next = merge(l1(4), l2(3,4))
…… 依次展开，直到某链表为空，然后开始逐层返回并连接。
复杂度分析： - **时间复杂度 O(n + m)**：同样每个节点访问一次。 - **空间复杂度 O(n + m)**：递归调用栈的深度最大为 n+m。这是递归解法的主要代价，对于超长链表可能存在栈溢出风险。
在“鳄鱼java”社区的算法精讲中，递归解法常被用来阐释如何将迭代的“命令式”思维转化为递归的“声明式”思维，即关注“要做什么”而非“一步步怎么做”。
四、迭代 vs 递归：深度对比与选择策略
深入理解LeetCode 021 合并两个有序链表的两种解法，能提升你的算法设计品味。
1. 思维模式差异： - **迭代**：是“自底向上”的构建过程。你关注于如何一步步移动指针，像搭积木一样构建出新链表。思维更贴近机器执行。 - **递归**：是“自顶向下”的分治过程。你先假设子问题（合并剩余链表）已经解决，然后只处理当前节点如何连接。思维更数学化、更抽象。
2. 性能与适用性： - **空间**：迭代法 O(1) 空间明显优于递归法 O(n+m)。在工程实践中，尤其是链表可能很长时，迭代法是首选。 - **代码简洁性**：递归法代码更短，逻辑更集中，体现了算法的数学美感。 - **理解难度**：递归解法要求对函数调用栈和链表引用有更深的理解，对初学者可能更具挑战。
3. 面试策略： 建议掌握两种方法。可以先阐述直观的迭代解法并写出代码，然后主动提出：“这个问题还有一个非常优雅的递归解法，它体现了分治的思想……” 这能展示你思维的广度。面试官可能会追问递归的缺点（栈空间），此时你对比分析两种方法，便能获得加分。
五、常见误区、边界条件与测试用例
编码常见坑点： 1. **丢失链表头**：迭代法中未使用哨兵节点，导致需要复杂的判空逻辑来初始化头节点。 2. **指针移动错误**：在连接节点后，忘记了移动 `curr` 指针，或移动了错误的链表指针。 3. **递归栈溢出**：对于极长的链表，递归解法可能抛出 `StackOverflowError`。
必须考虑的边界条件： - 两个链表都为空。 - 其中一个链表为空。 - 链表中有重复元素（题目已说明非递减，包含相等情况）。 - 链表长度差异极大（如一个很长，一个只有一个节点）。
自测用例建议： - `l1 = [], l2 = []` -> `[]` - `l1 = [], l2 = [0]` -> `[0]` - `l1 = [1,2,3], l2 = [4,5,6]` （一个完全大于另一个） - `l1 = [1,3,5], l2 = [2,4,6]` （交错有序）
六、从本题出发：进阶思考与关联题目
彻底掌握LeetCode 021 合并两个有序链表，是开启一系列高级链表和分治算法的大门。
直接进阶： - **LeetCode 23. 合并K个升序链表**：本题的升级版。核心思路是：1) 顺序两两合并（复用本题代码）；2) 使用优先队列（最小堆）优化；3) 分治合并（两两分组，再逐层合并），其分治思想正是本题递归解法的多维扩展。
思维扩展： - **如何合并两个有序数组？** 与链表不同，数组的合并通常需要额外的O(n+m)空间，或者从后向前遍历原地合并（对于有足够空间的情况）。 - **如果链表是降序的怎么办？** 逻辑完全一样，只是比较大小的方向可能调整，或者可以先反转链表再合并。
关联模式： 本题的“双指针有序合并”模式，也出现在其他数据结构中，如合并两个有序数组、计算两个有序数组的中位数等。
七、总结：掌握基础，方能驾驭复杂
LeetCode 021 合并两个有序链表是一道“教科书式”的题目。它迫使你直面链表操作的核心——指针（引用）的操纵，并提供了迭代与递归两种截然不同却又同样深刻的解决方案。
请记住，在面试中清晰地解释哨兵节点的作用、指针移动的每一步，或者递归函数的定义与缩减过程，远比默写代码更重要。这道题的精髓在于理解“有序”特性如何让我们能够以线性的时间完成合并。
现在，请你尝试在不看答案的情况下，分别用迭代和递归解决此问题。然后思考：如果题目要求合并的不是两个，而是K个有序链表（LeetCode 23），你能否将本题的解法作为基础模块，构建出效率更高的解决方案？这将是检验你是否真正内化本课内容的最佳实践。
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
