1. 问题描述与基础解法合并两个有序链表是LeetCode上经典的链表操作题目编号21难度标记为Easy。题目要求将两个按升序排列的链表合并为一个新的升序链表。新链表应该通过拼接原始链表的节点组成而不是创建新的节点。1.1 题目示例分析给定两个链表L1: 1 → 2 → 4L2: 1 → 3 → 4合并后的链表应该是1 → 1 → 2 → 3 → 4 → 4这个示例展示了几个关键点当两个链表当前节点值相等时第一个1可以任选一个先接入需要完整遍历两个链表直到所有节点都被处理不需要创建新节点直接改变next指针即可1.2 基础迭代解法最直观的解法是使用迭代法时间复杂度O(nm)空间复杂度O(1)def mergeTwoLists(l1, l2): dummy ListNode(-1) # 创建虚拟头节点 prev dummy while l1 and l2: if l1.val l2.val: prev.next l1 l1 l1.next else: prev.next l2 l2 l2.next prev prev.next # 处理剩余节点 prev.next l1 if l1 else l2 return dummy.next关键点说明使用dummy节点可以避免处理头节点的特殊情况循环条件是两个链表都非空每次比较当前节点值将较小的接入结果链表最后处理可能剩余的节点2. 递归解法与性能对比2.1 递归解法实现递归解法代码更简洁但理解难度稍高def mergeTwoLists(l1, l2): if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next mergeTwoLists(l1.next, l2) return l1 else: l2.next mergeTwoLists(l1, l2.next) return l22.2 两种解法的对比特性迭代法递归法时间复杂度O(nm)O(nm)空间复杂度O(1)O(nm)栈空间代码简洁度中等高适用场景长链表短链表可读性直观需要递归思维提示在实际面试中建议先给出迭代解法如果面试官要求再展示递归解法。递归虽然简洁但长链表可能导致栈溢出。3. 边界条件与异常处理3.1 常见边界情况一个链表为空直接返回另一个链表两个链表都为空返回空链表有重复值正常处理保持原顺序链表长度差异大确保能处理完较长链表的剩余部分3.2 防御性编程实践def mergeTwoLists(l1, l2): # 显式处理空链表情况 if not l1 or not l2: return l1 if l1 else l2 # 主逻辑保持不变 dummy ListNode(0) current dummy while l1 and 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 or l2 return dummy.next4. 链表操作的核心技巧4.1 虚拟头节点(dummy node)的应用虚拟头节点技巧是链表问题的通用解法可以简化头节点的特殊处理统一插入逻辑避免空指针异常创建和使用模式dummy ListNode(0) # 值任意不会被使用 current dummy # ...处理逻辑... return dummy.next # 返回真正的头节点4.2 指针操作的注意事项指针移动顺序先连接节点再移动指针循环终止条件明确是while l1 and l2还是or剩余节点处理使用简洁的l1 or l2表达式避免指针丢失在修改next前确保有备份4.3 链表遍历的常见模式# 标准遍历模板 current head while current: # 处理current节点 current current.next # 带前驱指针的遍历 prev None current head while current: # 处理current节点 prev current current current.next5. 相关题目拓展5.1 LeetCode相似题目23. 合并K个升序链表本题的进阶版可以使用优先队列或分治解法88. 合并两个有序数组数组合并版本需要从后向前处理148. 排序链表可以先拆分再合并使用归并排序思想160. 相交链表同样需要处理两个链表的遍历5.2 实际应用场景数据库归并操作合并两个有序结果集日志合并合并多个按时间排序的日志文件消息队列合并多个有序消息流版本控制系统合并两个分支的修改历史6. 常见错误与调试技巧6.1 典型错误案例无限循环忘记移动指针导致# 错误示例 current.next l1 # 忘记 l1 l1.next指针丢失修改next前没有备份# 错误示例 current.next l1 l1 l1.next # 如果先执行这个会丢失原l1.next头节点处理不当没有使用dummy节点导致复杂判断6.2 调试方法可视化工具使用Python Tutor等工具逐步执行打印链表实现辅助函数打印链表状态def print_list(head): while head: print(head.val, end - ) head head.next print(None)小样例测试从空链表、单节点链表等简单情况开始7. 不同语言的实现差异7.1 C实现要点class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; } };注意点使用指针和引用内存管理本题不需要显式释放结构体访问使用-操作符7.2 Java实现特点class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); 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; } }Java特点显式的null检查对象访问使用.操作符自动垃圾回收8. 性能优化与进阶思考8.1 内存访问模式优化现代CPU缓存对链表性能影响很大链表节点内存不连续缓存命中率低可以尝试预先分配节点池对于特别长的链表考虑转换为数组处理8.2 并行化可能性对于非常长的链表可以分段合并使用多线程处理不同区段最后合并各段结果8.3 实际工程中的变种稳定合并保持相等元素的原始顺序原地合并不适用额外空间较复杂多路合并扩展到多个链表的合并我在实际刷题中发现链表问题最重要的是画图分析指针变化。对于合并两个有序链表这样的基础题建议至少手写实现3-5遍直到能够闭眼写出无bug的代码。这是很多更复杂链表问题的基础比如合并K个链表、链表排序等都会用到这个核心操作。