【力扣100题】13.合并两个有序链表

一、题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4] 输入：l1 = [], l2 = [] 输出：[] 输入：l1 = [], l2 = [0] 输出：[0]

二、核心思路

关键思想：双指针 + 哑节点（哨兵节点）

两个链表都是升序的，我们可以用两个指针分别遍历两个链表，每次取较小的节点接到新链表末尾，直到其中一个链表遍历完，最后把剩余部分直接拼接。

迭代法步骤

1. 创建哑节点 dummy，作为新链表的头部前驱 2. 维护一个 cur 指针，指向新链表的当前尾节点 3. 当 list1 和 list2 都不为空时： - 比较当前两个节点的值 - 将较小节点接到 cur->next，并移动对应链表的指针 - cur 向后移动一位 4. 将未遍历完的链表直接接到 cur->next 5. 返回 dummy.next（真正的头节点）

三、代码实现

方法：迭代 + 哑节点 ✅

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy; // 哑节点，简化边界处理 ListNode* cur = &dummy; // cur 指向新链表的尾部 // 阶段1：两链表都有节点时，比较并接入较小者 while (list1 && list2) { if (list1->val < list2->val) { cur->next = list1; list1 = list1->next; } else { cur->next = list2; list2 = list2->next; } cur = cur->next; } // 阶段2：将剩余部分直接拼接 cur->next = list1 ? list1 : list2; return dummy.next; // 返回真正的头节点 } };

复杂度分析

四、图解全过程

示例：l1 = [1,2,4]，l2 = [1,3,4]

text

初始状态： dummy → null cur → dummy list1: 1 → 2 → 4 → null list2: 1 → 3 → 4 → null -------------------------------- 第1步：比较 list1.val(1) 和 list2.val(1) → 相等，取 list2（或 list1） cur->next = list2 (节点1) cur 移动到节点1 list2 后移 → 3 dummy → 1 → null cur → 1 list1: 1 → 2 → 4 list2: 3 → 4 -------------------------------- 第2步：比较 1 和 3 → 取 list1 cur->next = list1 (节点1) cur 移动到节点1 list1 后移 → 2 dummy → 1 → 1 → null cur → 1 list1: 2 → 4 list2: 3 → 4 -------------------------------- 第3步：比较 2 和 3 → 取 list1 cur->next = list1 (节点2) cur 移动到节点2 list1 后移 → 4 dummy → 1 → 1 → 2 → null cur → 2 list1: 4 list2: 3 → 4 -------------------------------- 第4步：比较 4 和 3 → 取 list2 cur->next = list2 (节点3) cur 移动到节点3 list2 后移 → 4 dummy → 1 → 1 → 2 → 3 → null cur → 3 list1: 4 list2: 4 -------------------------------- 第5步：比较 4 和 4 → 取 list1（或 list2） cur->next = list1 (节点4) cur 移动到节点4 list1 后移 → null dummy → 1 → 1 → 2 → 3 → 4 → null cur → 4 list1: null list2: 4 -------------------------------- 阶段2：list1 为空，将 list2 剩余部分直接拼接 cur->next = list2 (节点4) 最终链表： 1 → 1 → 2 → 3 → 4 → 4 → null

五、代码执行流程图

text

开始 │ ▼ 创建 dummy，cur = &dummy │ ▼ ┌─────────────────────────────────┐ │ while (list1 && list2) │ │ if list1->val < list2->val │ │ cur->next = list1 │ │ list1 = list1->next │ │ else │ │ cur->next = list2 │ │ list2 = list2->next │ │ cur = cur->next │ └───────────────┬─────────────────┘ │ (任一链表为空) ▼ cur->next = (list1 ? list1 : list2) │ ▼ return dummy.next

六、其他解法

方法2：递归（优雅但空间稍大）

cpp

ListNode* mergeTwoLists(ListNode* l1, ListNode* 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; } }

方法3：暴力（将节点放入数组排序再重建）—— 不推荐

cpp

ListNode* mergeTwoLists_brute(ListNode* l1, ListNode* l2) { vector<int> vals; while (l1) { vals.push_back(l1->val); l1 = l1->next; } while (l2) { vals.push_back(l2->val); l2 = l2->next; } sort(vals.begin(), vals.end()); ListNode dummy; ListNode* cur = &dummy; for (int v : vals) { cur->next = new ListNode(v); cur = cur->next; } return dummy.next; }

七、方法对比

八、完整测试代码

#include <iostream> #include <vector> using namespace std; struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy; ListNode* cur = &dummy; while (list1 && list2) { if (list1->val < list2->val) { cur->next = list1; list1 = list1->next; } else { cur->next = list2; list2 = list2->next; } cur = cur->next; } cur->next = list1 ? list1 : list2; return dummy.next; } }; // 辅助函数：从 vector 创建链表 ListNode* createList(const vector<int>& vals) { ListNode dummy; ListNode* cur = &dummy; for (int v : vals) { cur->next = new ListNode(v); cur = cur->next; } return dummy.next; } // 辅助函数：打印链表 void printList(ListNode* head) { while (head) { cout << head->val; if (head->next) cout << " -> "; head = head->next; } cout << endl; } int main() { Solution sol; // 测试1 ListNode* l1 = createList({1,2,4}); ListNode* l2 = createList({1,3,4}); ListNode* merged = sol.mergeTwoLists(l1, l2); cout << "测试1: "; printList(merged); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 // 测试2 ListNode* l3 = createList({}); ListNode* l4 = createList({}); ListNode* merged2 = sol.mergeTwoLists(l3, l4); cout << "测试2: "; printList(merged2); // (空) // 测试3 ListNode* l5 = createList({}); ListNode* l6 = createList({0}); ListNode* merged3 = sol.mergeTwoLists(l5, l6); cout << "测试3: "; printList(merged3); // 0 return 0; }

输出：

测试1: 1 -> 1 -> 2 -> 3 -> 4 -> 4 测试2: 测试3: 0

九、总结

核心技巧：哑节点（哨兵）
使用哑节点可以统一处理头节点的插入逻辑，避免对空链表的特殊判断，让代码更简洁优雅。

适用场景：任何需要合并两个有序序列的问题（数组、链表等）都可以借鉴此双指针思路。