LeetCode 21题 "合并两个有序链表" 是链表操作的经典入门题，题目要求将两个升序排列的链表合并为一个新的升序链表并返回。这个问题看似简单，却蕴含了链表操作的核心思想，包括指针移动、节点连接和边界处理。
题目给出的示例非常直观：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
这道题的价值在于它的解法多样性和可拓展性。无论是迭代法还是递归法，都能很好地训练我们的逻辑思维能力。而且掌握了这道题的解法后，我们还能将其拓展应用到"合并K个有序链表"等更复杂的问题中。
链表结构基础：为什么链表操作需要特殊技巧
在讲解具体解法之前，我们需要先回顾一下链表的基本结构。与数组不同，链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
每个链表节点包含两个部分：
数据域：存储数据元素
指针域：存储下一个节点的指针
这种结构使得链表在插入和删除操作上比数组更高效，但也带来了一些操作上的复杂性。比如在我们今天要解决的合并问题中，我们需要小心地处理指针的指向，避免出现断链或循环引用的情况。
迭代法详解：最直观的链表合并思路
迭代法是解决这个问题最直观的思路，它的核心思想是创建一个新的链表，然后依次比较两个输入链表的节点值，将较小的节点添加到新链表中。
具体步骤如下：
创建一个虚拟头节点(dummy head)，这可以简化边界情况的处理
维护一个当前指针，用于构建新链表
同时遍历两个输入链表，比较当前节点值
将较小的节点接到当前指针后面，并移动相应的指针
当一个链表遍历完后，将另一个链表的剩余部分接到新链表末尾
下面是Python实现代码：
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:# 创建虚拟头节点dummy = ListNode(-1)current = dummy# 同时遍历两个链表while l1 and l2:if l1.val <= l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.next# 处理剩余节点current.next = l1 if l1 else l2return dummy.next
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; }}class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(-1);ListNode current = dummy;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}current.next = l1 != null ? l1 : l2;return dummy.next;}}
JavaScript实现：
function ListNode(val, next) {this.val = (val===undefined ? 0 : val)this.next = (next===undefined ? null : next)}var mergeTwoLists = function(l1, l2) {const dummy = new ListNode(-1);let current = dummy;while (l1 && l2) {if (l1.val <= l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}current.next = l1 || l2;return dummy.next;};
迭代法的时间复杂度是O(n + m)，其中n和m分别是两个输入链表的长度。空间复杂度是O(1)，因为我们只使用了常数级别的额外空间。
递归法详解：用数学归纳法理解链表合并
递归法虽然不如迭代法直观，但它提供了一种更优雅的解决方案。递归的核心思想是将大问题分解为小问题：要合并两个链表，我们可以先比较它们的头节点，然后递归地合并剩余的节点。
递归思路：
基线条件：如果其中一个链表为空，返回另一个链表
递归条件：比较两个链表的头节点值
将较小节点的next指向合并剩余节点的结果
返回较小的节点
Python实现代码：
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:# 基线条件if not l1:return l2if not l2:return l1# 递归条件if l1.val <= l2.val:l1.next = mergeTwoLists(l1.next, l2)return l1else:l2.next = mergeTwoLists(l1, l2.next)return l2
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;}}}
JavaScript实现：
var mergeTwoLists = function(l1, l2) {// 基线条件if (!l1) return l2;if (!l2) return l1;// 递归条件if (l1.val <= l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}};
递归法的时间复杂度同样是O(n + m)，但空间复杂度是O(n + m)，因为递归调用会占用栈空间，递归深度最多为n + m。
边界情况处理：这些特殊情况你考虑到了吗
在解决链表问题时，边界情况的处理尤为重要。对于合并两个有序链表的问题，我们需要考虑以下几种特殊情况：
其中一个链表为空
解决方案：直接返回另一个链表
两个链表都为空
解决方案：返回空链表
一个链表是另一个链表的前缀
例如：l1 = [1,2,3], l2 = [4,5,6]
解决方案：迭代法中自然处理，当一个链表遍历完后，将另一个链表的剩余部分接到新链表末尾
链表中存在重复元素
例如：l1 = [1,1,2], l2 = [1,3,4]
解决方案：比较时使用<=，保证稳定性
其中一个链表只有一个节点
解决方案：迭代法和递归法都能自然处理
算法优化与拓展：从合并两个到合并K个
掌握了合并两个有序链表的方法后，我们可以思考如何将其拓展应用到更复杂的问题中。最典型的拓展就是"合并K个有序链表"(LeetCode 23题)。
有两种主要思路可以解决这个问题：
顺序合并：重复应用合并两个有序链表的函数，依次合并所有链表
时间复杂度：O(k^2 * n)，其中k是链表数量，n是平均长度
空间复杂度：O(1)
分治合并：将K个链表分成两半，递归合并每一半，最后合并两个结果
时间复杂度：O(k * n * log k)
空间复杂度：O(log k)，递归调用栈的深度
下面是分治合并的Python实现思路：
def mergeKLists(lists):if not lists:return Nonereturn merge_range_lists(lists, 0, len(lists) - 1)def merge_range_lists(lists, left, right):if left == right:return lists[left]mid = (left + right) // 2l1 = merge_range_lists(lists, left, mid)l2 = merge_range_lists(lists, mid + 1, right)return mergeTwoLists(l1, l2) # 这里调用我们之前实现的合并两个链表的函数
除了分治算法，我们还可以使用优先队列(最小堆)来解决合并K个有序链表的问题：
将所有链表的头节点加入优先队列
取出最小节点加入结果链表
如果该节点有下一个节点，将其加入优先队列
重复步骤2和3，直到优先队列为空
这种方法的时间复杂度是O(k * n * log k)，空间复杂度是O(k)。
总结与思考：这道题教会我们什么
LeetCode 21题虽然看似简单，但它蕴含了很多重要的算法思想和编程技巧：
虚拟头节点技巧：这是链表操作中非常常用的技巧，可以简化边界情况的处理，避免对头节点进行特殊判断。
迭代 vs 递归：同一问题往往有多种解法，迭代法通常更高效，而递归法更简洁优雅。理解两种方法的优缺点和适用场景，有助于我们在实际问题中做出正确选择。
分治思想：将大问题分解为小问题，解决小问题后合并结果，这种思想在很多算法中都有应用，如排序算法中的归并排序、快速排序等。
边界情况处理：在编写代码时，充分考虑各种边界情况，能让我们的程序更加健壮。
这道题虽然简单，但它是很多复杂链表问题的基础。掌握了它的解法，我们就能更好地理解和解决更复杂的链表问题，如合并K个有序链表、排序链表等。
最后，我想强调的是，算法学习不仅是为了解题，更是为了培养一种解决问题的思维方式。希望通过这道题的讲解，大家不仅能掌握合并有序链表的方法，更能理解背后的算法思想，将其应用到更广泛的问题中去。