【数据结构与算法】21.合并两个有序链表(LeetCode)
文章目录
合并两个有序链表：高效算法解析与实现
链表合并是数据结构中的经典问题，在算法面试和实际开发中经常出现。本文将深入解析如何高效合并两个有序链表，并展示C语言的实现方案。
问题描述
给定两个升序排列的链表list1和list2，要求将它们合并为一个新的升序链表并返回。新链表应该通过拼接给定链表的节点来完成。
示例：
输入：list1 = [1,2,4], list2 = [1,3,4] 输出：[1,1,2,3,4,4] 核心思路：双指针尾插法
基本思想：
- 创建一个新的空链表作为结果
- 使用两个指针分别遍历两个输入链表
- 比较当前节点的值，将较小值的节点插入新链表的尾部
- 当任一链表遍历完后，将剩余链表直接接到新链表尾部
时间复杂度： O(n+m)，其中n和m分别是两个链表的长度
空间复杂度： O(1)，不需要额外空间，直接在原节点上操作
完整代码实现
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){structListNode* l1 = list1;structListNode* l2 = list2;structListNode* NewHead =NULL;structListNode* NewTail =NULL;// 处理空链表的情况if(l1 ==NULL)return l2;if(l2 ==NULL)return l1;// 遍历两个链表while(l1 && l2){if(l1->val < l2->val){// 处理新链表的头节点if(NewHead ==NULL){ NewHead = NewTail = l1;}else{ NewTail->next = l1; NewTail = NewTail->next;} l1 = l1->next;}else{// 处理新链表的头节点if(NewHead ==NULL){ NewHead = NewTail = l2;}else{ NewTail->next = l2; NewTail = NewTail->next;} l2 = l2->next;}}// 连接剩余链表if(l1 ==NULL){ NewTail->next = l2;}else{ NewTail->next = l1;}return NewHead;}关键点解析
1. 边界条件处理
if (l1 == NULL) return l2; if (l2 == NULL) return l1; 这两行代码处理了空链表的边界情况，提高了代码的健壮性。
2. 头节点初始化
if (NewHead == NULL) { NewHead = NewTail = l1; // 或l2 } 这里使用NewHead和NewTail两个指针分别记录新链表的头和尾：
NewHead：始终指向新链表的头节点NewTail：始终指向新链表的尾节点，便于尾插操作
3. 节点比较与插入
if (l1->val < l2->val) { // 插入l1节点 } else { // 插入l2节点 } 通过比较两个链表当前节点的值，决定哪个节点应该优先插入新链表，确保结果保持升序。
4. 剩余节点处理
if (l1 == NULL) { NewTail->next = l2; } else { NewTail->next = l1; } 当任一链表遍历完后，直接将另一链表的剩余部分连接到新链表尾部，避免了不必要的循环。
常见错误与修正
在原始代码中，存在一个典型错误：
// 错误写法（赋值而非比较）if(NewHead=NULL)// 正确写法（比较操作）if(NewHead ==NULL)这个错误会导致：
- 将
NewHead设置为NULL - 条件判断结果永远为假（
NULL相当于0） - 永远不会进入头节点初始化分支
开发建议： 在条件判断中使用常量在前的方式避免此类错误：
if(NULL== NewHead)// 如果误写为赋值，编译器会报错优化方案：哨兵节点
使用哨兵节点可以进一步简化代码逻辑：
structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){structListNode dummy;// 哨兵节点structListNode* tail =&dummy; dummy.next =NULL;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个分支减少到2个）
- 提高代码可读性和健壮性
- 避免头节点指针的初始化问题
算法应用场景
- 归并排序：链表归并排序的核心操作
- 多路归并：多个有序流的合并（如K个有序链表）
- 数据库系统：合并多个有序结果集
- 消息队列：合并多个有序消息流
总结
合并两个有序链表是链表操作中的基础但重要的算法：
- 核心思想：双指针遍历+尾插法
- 关键技巧：头尾指针维护新链表
- 常见陷阱：头节点初始化、指针操作顺序
- 优化方向：哨兵节点简化边界处理
多路归并*：多个有序流的合并（如K个有序链表）
3. 数据库系统：合并多个有序结果集
4. 消息队列：合并多个有序消息流
总结
合并两个有序链表是链表操作中的基础但重要的算法：
- 核心思想：双指针遍历+尾插法
- 关键技巧：头尾指针维护新链表
- 常见陷阱：头节点初始化、指针操作顺序
- 优化方向：哨兵节点简化边界处理
