一、题目完整描述题目要求给定两个非递减升序排列的单链表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 ≤ 1003. 两个输入链表均为非递减有序后一个节点值 ≥ 前一个节点值二、零基础必备前置知识本题是链表入门核心题所有知识点从零讲解零基础可完全看懂所有概念、特性、操作全部讲透。1. 什么是链表对比数组理解1.1 数组的特点铺垫对比我们平时接触的列表/数组是连续内存存储。比如数组[1,2,4]三个数字在内存中是紧紧挨在一起的可以通过下标0、1、2直接找到任意元素。数组缺点插入、删除元素时需要移动大量元素效率低固定长度灵活性差。1.2 单链表的定义链表是非连续内存存储的线性数据结构。简单来说链表由无数个「节点」串联而成每个节点只认识自己的下一个节点。单链表是最基础的链表类型只能从头向尾遍历不能反向遍历。2. 链表节点的完整结构本题用到的所有链表节点固定包含两个核心属性C和Python定义完全对应2.1 属性1val数值域存储当前节点的具体数值就是题目中我们需要排序、合并的数字。2.2 属性2next指针/引用域这是链表的灵魂next 存储的是「下一个节点的地址/引用」用来连接下一个节点。特殊值空值CnullptrPythonNone代表当前节点是链表的最后一个节点后面没有节点了。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; // 无参构造创建空节点值为0next为空 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(vectorint 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, val0, nextNone): 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) → curdummylist11list21第1轮循环list1.val(1) list2.val(1) → 拼接list2节点list2后移为3cur后移新链表-1→1第2轮循环list1.val(1) list2.val(3) → 拼接list1节点list1后移为2cur后移新链表-1→1→1第3轮循环list1.val(2) list2.val(3) → 拼接list1节点list1后移为4cur后移新链表-1→1→1→2第4轮循环list1.val(4) list2.val(3) → 拼接list2节点list2后移为4cur后移新链表-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(vectorint 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) { // 递归终止条件1list1为空直接返回list2剩余节点 if (list1 nullptr) return list2; // 递归终止条件2list2为空直接返回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, val0, nextNone): 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)层111保留右侧1调用merge(1→2→4, 3→4)层213保留左侧1调用merge(2→4, 3→4)层323保留左侧2调用merge(4, 3→4)层443保留右侧3调用merge(4,4)层544保留右侧4调用merge(4, null)层6触发终止条件返回4逐层回溯拼接最终生成完整有序链表六、两种解法复杂度深度分析解法时间复杂度空间复杂度优缺点总结迭代法O(nm)O(1)最优解仅用常数级指针空间逻辑直观无栈溢出风险面试首选递归法O(nm)O(nm)代码简洁逻辑抽象占用递归栈空间节点过多可能栈溢出适合学习思想注n、m 分别为两个输入链表的节点总数两种解法均需要遍历所有节点时间效率一致七、高频易错点总结避坑必看1.忘记处理空链表未判断链表为空会导致空指针报错本题所有边界均已覆盖2.不使用哨兵节点手动判断头节点极易出现头节点丢失、拼接错乱问题3.循环结束忘记拼接剩余节点两个链表长度不同剩余有序节点必须直接拼接否则数据丢失4.递归无终止条件会造成无限递归、程序崩溃必须优先判断空链表终止