一、题目完整描述
题目要求
给定两个非递减升序排列的单链表list1和list2，请你将两个链表合并为一个全新的非递减升序链表。合并规则为：直接拼接两个链表的原有所有节点，不新建额外数据节点，最终返回合并后新链表的头节点。
题目示例
示例1：输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例2：输入：l1 = [], l2 = [] 输出：[]
示例3：输入：l1 = [], l2 = [0] 输出：[0]
题目约束
1. 两个链表的节点数量范围：[0, 50]（支持空链表）
2. 节点数值范围：-100 ≤ Node.val ≤ 100
3. 两个输入链表均为非递减有序（后一个节点值 ≥ 前一个节点值）
二、零基础必备前置知识
本题是链表入门核心题，所有知识点从零讲解，零基础可完全看懂，所有概念、特性、操作全部讲透。
1. 什么是链表？（对比数组理解）
1.1 数组的特点（铺垫对比）
我们平时接触的列表/数组，是连续内存存储。比如数组[1,2,4]，三个数字在内存中是紧紧挨在一起的，可以通过下标0、1、2直接找到任意元素。
数组缺点：插入、删除元素时，需要移动大量元素，效率低；固定长度，灵活性差。
1.2 单链表的定义
链表是非连续内存存储的线性数据结构。简单来说：链表由无数个「节点」串联而成，每个节点只认识自己的下一个节点。
单链表是最基础的链表类型，只能从头向尾遍历，不能反向遍历。
2. 链表节点的完整结构
本题用到的所有链表节点，固定包含两个核心属性，C++和Python定义完全对应：
2.1 属性1：val（数值域）
存储当前节点的具体数值，就是题目中我们需要排序、合并的数字。
2.2 属性2：next（指针/引用域）
这是链表的灵魂！next 存储的是「下一个节点的地址/引用」，用来连接下一个节点。
特殊值：空值（C++：nullptr，Python：None），代表当前节点是链表的最后一个节点，后面没有节点了。
2.3 节点可视化示例
节点(1) → 节点(2) → 节点(4) → 空
解读：数值为1的节点，next指向数值为2的节点；数值为2的节点，next指向数值为4的节点；数值为4的节点，next为空，是尾节点。
3. 关键基础概念
3.1 空链表
没有任何节点的链表，直接等于nullptr/None，对应题目输入[]，是本题高频边界条件。
3.2 有序链表（非递减链表）
题目核心条件：输入的两个链表都是非递减有序。含义：链表中后一个节点的 val 永远大于等于前一个节点的 val。
示例：1→2→4、1→3→4都是合法输入，无需我们排序，只需要合并有序链表。
3.3 链表的核心操作（本题全部用到）
① 链表遍历：从链表头节点开始，通过next不断向后移动，直到遇到空值停止。
② 链表拼接：修改节点的next指向，让当前节点连接另一个节点，实现链表合并。
③ 指针移动：用一个临时指针变量，记录当前操作的节点，遍历过程中不断后移。
4. 哨兵节点
定义：哨兵节点（虚拟头节点）是一个无实际数值意义的临时节点，不存储有效数据，专门用来解决链表头节点边界问题。
为什么要用哨兵？
如果不使用哨兵，合并时需要单独判断「头节点是谁」（哪个链表的第一个节点更小），代码繁琐、边界易错。
使用哨兵后：所有节点统一通过拼接方式添加，无需单独处理头节点，代码逻辑统一、零边界bug。
使用规则：最终结果丢弃哨兵节点，返回哨兵节点的下一个节点（真正的链表头）。
5. 递归基础（进阶解法必备）
递归核心：把大问题拆解为相同逻辑的小问题，直到触发终止条件，再逐层返回结果。
递归三要素：终止条件、递推逻辑、返回值。本题递归就是「合并两个链表」的子问题拆解。
三、解题思路总览（由易到难）
本题提供两种标准解法，难度从低到高排序，适配不同学习阶段：
解法一：迭代法（首选、最优解）- 逻辑直观、无递归、空间复杂度O(1)，面试最推荐
解法二：递归法（进阶解法）- 代码极简、逻辑抽象、利用系统栈，适合进阶学习
四、解法一：迭代法（超详细讲解+完整可运行代码）
1. 核心解题原理
利用哨兵节点 + 双指针遍历，同时遍历两个有序链表，每次选取两个链表中当前值更小的节点，拼接到新链表尾部，直到其中一个链表遍历完毕，最后将剩余未遍历的链表直接拼接在新链表末尾。
2. 分步算法流程（大白话逐步骤）
步骤1：创建虚拟哨兵节点，作为新链表的临时起点；
步骤2：定义cur指针，指向哨兵节点，负责记录新链表的当前尾部位置；
步骤3：循环遍历两个输入链表，只要两个链表都还有节点，就对比当前头节点数值；
步骤4：将数值更小的节点拼接在cur指针后面，同时该链表头指针后移、cur指针后移；
步骤5：当任意一个链表遍历为空，停止循环；
步骤6：将非空的剩余链表直接拼接在cur指针尾部（剩余链表本身有序，无需遍历）；
步骤7：返回哨兵节点的下一个节点，即为合并后的完整有序链表。
3. C++ 完整可运行代码（逐行超详细注释+自测主函数）
该代码可直接复制运行，包含：节点定义、合并算法、自定义链表构建函数、链表打印函数、主函数测试（题目示例+自定义输入测试）
// 引入标准输入输出头文件，用于自定义输入输出测试 #include <iostream> #include <vector> using namespace std; // 【链表节点结构体定义】题目标准定义，零基础必懂 struct ListNode { // 节点存储的数值 int val; // 指向下一个节点的指针，初始为空 ListNode *next; // 无参构造：创建空节点，值为0，next为空 ListNode() : val(0), next(nullptr) {} // 单参构造：创建指定数值的节点，next为空（尾节点） ListNode(int x) : val(x), next(nullptr) {} // 全参构造：创建指定数值、指定下一个节点的节点 ListNode(int x, ListNode *next) : val(x), next(next) {} }; // 【工具函数1：通过数组快速构建链表】方便自定义测试 ListNode* createList(vector<int> nums) { // 空数组直接返回空链表 if (nums.empty()) return nullptr; // 创建哨兵节点，简化构建逻辑 ListNode* dummy = new ListNode(); // cur指针记录当前尾部节点 ListNode* cur = dummy; // 遍历数组，逐个创建节点拼接 for (int num : nums) { cur->next = new ListNode(num); cur = cur->next; } // 返回真实头节点 return dummy->next; } // 【工具函数2：打印链表】可视化输出结果，方便查看测试效果 void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { cout << cur->val << " "; cur = cur->next; } cout << endl; } // 【核心算法：合并两个有序链表】迭代法 class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { // 1. 创建哨兵虚拟头节点，无实际数值，解决头节点边界问题 ListNode* dummy = new ListNode(-1); // 2. cur指针：始终指向新链表的【最后一个节点】，用于拼接新节点 ListNode* cur = dummy; // 3. 循环遍历：两个链表都不为空时，持续对比拼接 while (list1 != nullptr && list2 != nullptr) { // 对比两个链表当前头节点的数值 if (list1->val < list2->val) { // list1节点更小：拼接list1当前节点到新链表尾部 cur->next = list1; // list1指针后移，准备下一次对比 list1 = list1->next; } else { // list2节点更小或相等：拼接list2当前节点到新链表尾部 cur->next = list2; // list2指针后移，准备下一次对比 list2 = list2->next; } // 新链表尾部指针后移，等待拼接下一个节点 cur = cur->next; } // 4. 处理剩余节点：一个链表遍历完，直接拼接另一个链表的剩余部分 // 三目运算符：list1为空则接list2，否则接list1 cur->next = (list1 == nullptr) ? list2 : list1; // 5. 返回新链表真实头节点（跳过哨兵节点） return dummy->next; } }; // 【主函数：所有测试用例执行入口，支持自定义输入】 int main() { Solution sol; // 测试用例1：题目示例1 l1=[1,2,4], l2=[1,3,4] cout << "测试用例1结果："; ListNode* l1 = createList({1,2,4}); ListNode* l2 = createList({1,3,4}); printList(sol.mergeTwoLists(l1, l2)); // 测试用例2：题目示例2 两个空链表 cout << "测试用例2结果："; ListNode* l3 = createList({}); ListNode* l4 = createList({}); printList(sol.mergeTwoLists(l3, l4)); // 测试用例3：题目示例3 一空一非空 cout << "测试用例3结果："; ListNode* l5 = createList({}); ListNode* l6 = createList({0}); printList(sol.mergeTwoLists(l5, l6)); // 自定义测试用例：负数、多节点测试 cout << "自定义测试用例结果："; ListNode* l7 = createList({-5,0,2}); ListNode* l8 = createList({-3,1,4,6}); printList(sol.mergeTwoLists(l7, l8)); return 0; }4. Python 完整可运行代码（逐行超详细注释+自测主函数）
完全适配Python3，可直接运行，包含工具函数、核心算法、多组测试用例、自定义输入
# 导入类型注解工具，规范代码格式 from typing import Optional, List # 【链表节点类定义】题目标准定义，零基础必懂 class ListNode: # 节点初始化方法：默认值0，默认无下一个节点 def __init__(self, val=0, next=None): self.val = val # 节点数值 self.next = next # 下一个节点引用 # 【工具函数1：数组转链表】自定义测试专用 def create_list(nums: List[int]) -> Optional[ListNode]: # 空数组返回空链表 if not nums: return None # 创建虚拟头节点 dummy = ListNode() cur = dummy # 遍历数组批量创建节点 for num in nums: cur.next = ListNode(num) cur = cur.next return dummy.next # 【工具函数2：打印链表】可视化输出结果 def print_list(head: Optional[ListNode]) -> None: res = [] cur = head while cur: res.append(str(cur.val)) cur = cur.next print(" ".join(res)) # 【核心算法：迭代法合并有序链表】 class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: # 1. 创建哨兵虚拟节点，统一拼接逻辑，规避头节点边界问题 dummy = ListNode(-1) # 2. cur指针：记录新链表的当前尾部位置，初始指向哨兵 cur = dummy # 3. 双链表同时遍历，均非空时循环对比 while list1 and list2: # 选取数值更小的节点拼接 if list1.val < list2.val: # 拼接list1当前节点 cur.next = list1 # list1指针后移 list1 = list1.next else: # 拼接list2当前节点 cur.next = list2 # list2指针后移 list2 = list2.next # 新链表尾部后移，等待下一次拼接 cur = cur.next # 4. 拼接剩余未遍历的节点（有序直接拼接，无需循环） cur.next = list1 if list1 else list2 # 5. 返回真实合并后的链表头节点 return dummy.next # 【主函数：批量测试所有用例+自定义测试】 if __name__ == "__main__": sol = Solution() # 题目示例1测试 print("测试用例1结果：", end="") l1 = create_list([1,2,4]) l2 = create_list([1,3,4]) print_list(sol.mergeTwoLists(l1, l2)) # 题目示例2测试 print("测试用例2结果：", end="") l3 = create_list([]) l4 = create_list([]) print_list(sol.mergeTwoLists(l3, l4)) # 题目示例3测试 print("测试用例3结果：", end="") l5 = create_list([]) l6 = create_list([0]) print_list(sol.mergeTwoLists(l5, l6)) # 自定义复杂测试用例（含负数、递增节点） print("自定义测试用例结果：", end="") l7 = create_list([-1,2,5,7]) l8 = create_list([0,3,6,8]) print_list(sol.mergeTwoLists(l7, l8))5. 逐行运行流程模拟（以示例1为例：l1=[1,2,4], l2=[1,3,4]）
初始状态：dummy(-1) → cur=dummy，list1=1，list2=1
第1轮循环：list1.val(1) == list2.val(1) → 拼接list2节点，list2后移为3，cur后移，新链表：-1→1
第2轮循环：list1.val(1) < list2.val(3) → 拼接list1节点，list1后移为2，cur后移，新链表：-1→1→1
第3轮循环：list1.val(2) < list2.val(3) → 拼接list1节点，list1后移为4，cur后移，新链表：-1→1→1→2
第4轮循环：list1.val(4) > list2.val(3) → 拼接list2节点，list2后移为4，cur后移，新链表：-1→1→1→2→3
第5轮循环：list1.val(4) == list2.val(4) → 拼接list2节点，list2后移为空，循环结束
收尾：list2为空，拼接剩余list1(4)，最终链表：1→1→2→3→4→4
五、解法二：递归法（进阶讲解+完整可运行代码）
1. 递归核心原理
递归核心思想：分治思想，将「合并两个长链表」拆解为「合并两个子链表」，层层递归，直到触发终止条件，再逐层回溯拼接结果。
2. 递归三要素
终止条件：任意一个链表为空，直接返回另一个链表（无需合并，剩余链表直接作为结果）
递推逻辑：对比两个链表头节点，保留数值更小的节点，让该节点的next指向「剩余两个链表的合并结果」
返回值：每一层递归返回当前层最小的节点，最终拼接成完整链表
3. C++ 完整可运行递归代码（带注释+测试主函数）
#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) {} }; // 数组构建链表工具函数 ListNode* createList(vector<int> nums) { if (nums.empty()) return nullptr; ListNode* dummy = new ListNode(); ListNode* cur = dummy; for (int num : nums) { cur->next = new ListNode(num); cur = cur->next; } return dummy->next; } // 链表打印工具函数 void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { cout << cur->val << " "; cur = cur->next; } cout << endl; } // 递归解法核心算法 class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { // 递归终止条件1：list1为空，直接返回list2剩余节点 if (list1 == nullptr) return list2; // 递归终止条件2：list2为空，直接返回list1剩余节点 if (list2 == nullptr) return list1; // 对比两个链表头节点，选取更小的节点递归拼接 if (list1->val < list2->val) { // list1节点更小：当前节点的next = 剩余list1和完整list2的合并结果 list1->next = mergeTwoLists(list1->next, list2); // 返回当前最小节点 return list1; } else { // list2节点更小或相等：当前节点的next = 完整list1和剩余list2的合并结果 list2->next = mergeTwoLists(list1, list2->next); // 返回当前最小节点 return list2; } } }; // 测试主函数 int main() { Solution sol; cout << "示例1结果："; printList(sol.mergeTwoLists(createList({1,2,4}), createList({1,3,4}))); cout << "示例2结果："; printList(sol.mergeTwoLists(createList({}), createList({}))); cout << "示例3结果："; printList(sol.mergeTwoLists(createList({}), createList({0}))); cout << "自定义测试结果："; printList(sol.mergeTwoLists(createList({-2,1,3}), createList({-1,2,4}))); return 0; }4. Python 完整可运行递归代码（带注释+测试主函数）
from typing import Optional, List # 链表节点定义 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next # 数组转链表工具函数 def create_list(nums: List[int]) -> Optional[ListNode]: if not nums: return None dummy = ListNode() cur = dummy for num in nums: cur.next = ListNode(num) cur = cur.next return dummy.next # 链表打印工具函数 def print_list(head: Optional[ListNode]) -> None: res = [] cur = head while cur: res.append(str(cur.val)) cur = cur.next print(" ".join(res)) # 递归核心算法 class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: # 递归终止条件：空链表直接返回另一个 if not list1: return list2 if not list2: return list1 # 递归递推逻辑：选小节点，递归合并剩余部分 if list1.val < list2.val: # 当前list1节点保留，后续节点由剩余链表合并生成 list1.next = self.mergeTwoLists(list1.next, list2) return list1 else: # 当前list2节点保留，后续节点由剩余链表合并生成 list2.next = self.mergeTwoLists(list1, list2.next) return list2 # 批量测试 if __name__ == "__main__": sol = Solution() print("示例1结果：", end="") print_list(sol.mergeTwoLists(create_list([1,2,4]), create_list([1,3,4]))) print("示例2结果：", end="") print_list(sol.mergeTwoLists(create_list([]), create_list([]))) print("示例3结果：", end="") print_list(sol.mergeTwoLists(create_list([]), create_list([0]))) print("自定义测试结果：", end="") print_list(sol.mergeTwoLists(create_list([-3,0,5]), create_list([-2,2,4])))5. 递归逐层调用流程（示例1）
初始调用：merge(1→2→4, 1→3→4)
层1：1=1，保留右侧1，调用merge(1→2→4, 3→4)
层2：1<3，保留左侧1，调用merge(2→4, 3→4)
层3：2<3，保留左侧2，调用merge(4, 3→4)
层4：4>3，保留右侧3，调用merge(4,4)
层5：4=4，保留右侧4，调用merge(4, null)
层6：触发终止条件，返回4
逐层回溯拼接，最终生成完整有序链表
六、两种解法复杂度深度分析
解法 | 时间复杂度 | 空间复杂度 | 优缺点总结 |
|---|---|---|---|
迭代法 | O(n+m) | O(1) | 最优解，仅用常数级指针空间，逻辑直观，无栈溢出风险，面试首选 |
递归法 | O(n+m) | O(n+m) | 代码简洁，逻辑抽象，占用递归栈空间，节点过多可能栈溢出，适合学习思想 |
注：n、m 分别为两个输入链表的节点总数，两种解法均需要遍历所有节点，时间效率一致
七、高频易错点总结（避坑必看）
1.忘记处理空链表：未判断链表为空会导致空指针报错，本题所有边界均已覆盖
2.不使用哨兵节点：手动判断头节点，极易出现头节点丢失、拼接错乱问题
3.循环结束忘记拼接剩余节点：两个链表长度不同，剩余有序节点必须直接拼接，否则数据丢失
4.递归无终止条件：会造成无限递归、程序崩溃，必须优先判断空链表终止
