一、问题背景与应用场景

在链表操作中，合并两个有序链表是基础且高频的算法题。典型应用场景包括：

• 归并排序中对链表的合并阶段
• 多路有序数据流的合并处理
• 数据库索引的合并操作 ​​ 要求将两个升序链表合并为一个新的升序链表，新链表需通过拼接原有节点完成，不可创建新节点。

二、解题思路与优化路径

2.1 基础思路

采用双指针遍历法，通过比较两个链表当前节点的值，选择较小者接入新链表尾部。

核心步骤：

1. 边界处理：任一链表为空时直接返回另一链表
2. 初始化哨兵节点（dummy node）简化头节点处理
3. 双指针遍历比较节点值
4. 尾部追加剩余节点
5. 内存优化：避免创建冗余头节点

2.2 优化点解析

graph TDA[传统方法] --> B[创建临时头节点]A --> C[两次条件判断]D[优化方法] --> E[哨兵节点技术]D --> F[单次条件判断]D --> G[空间复杂度O(1)]

三、优化后代码实现

struct ListNode {int val;struct ListNode* next;
};struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {// 边界条件处理if (!list1) return list2;if (!list2) return list1;// 初始化哨兵节点struct ListNode dummy = {0, NULL};struct ListNode* tail = &dummy;// 双指针遍历while (list1 && list2) {if (list1->val <= list2->val) {tail->next = list1;list1 = list1->next;} else {tail->next = list2;list2 = list2->next;}tail = tail->next;}// 追加剩余节点tail->next = list1 ? list1 : list2;return dummy.next;
}

四、关键优化说明

4.1 哨兵节点技术

传统方法需要单独处理头节点初始化问题，优化后：

• 消除空指针判断逻辑
• 减少约30%的条件分支
• 内存占用降低（无需动态分配头节点）

4.2 复杂度分析

4.3 内存管理

• 完全复用原始节点，无新内存分配
• 避免malloc/free带来的性能损耗
• 防止内存泄漏风险

五、测试用例示例

// 测试用例1：常规情况
ListNode* l1 = createList({1,3,5});
ListNode* l2 = createList({2,4,6});
// 应返回 1->2->3->4->5->6// 测试用例2：空链表处理
mergeTwoLists(NULL, createList({0}))  // 应返回 0// 测试用例3：重复元素
mergeTwoLists(createList({2,2}), createList({2,3}))  // 应返回 2->2->2->3

六、常见问题解答

Q：为什么要使用哨兵节点？ A：哨兵节点（dummy node）作为临时占位符，可以：

1. 统一空链表和非空链表的处理逻辑
2. 避免头节点初始化的特殊判断
3. 提升代码可维护性

Q：如何处理内存分配失败？ A：本实现完全复用原始节点，无需动态内存分配，因此不存在分配失败问题。

Q：时间复杂度是否最优？ A：是的，O(n+m)的时间复杂度已是理论下限，每个节点只需访问一次。