链表---有序链表

个人主页Milestone-里程碑❄️个人专栏: 力扣hot100 CLinuxGitMySQL心向往之行必能至题目描述将两个升序的单链表合并为一个新的升序单链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的不允许额外创建新节点只能复用原节点。示例plaintext输入list1 [1,2,4], list2 [1,3,4] 输出[1,1,2,3,4,4]解题思路这道题是链表操作的经典入门题核心思路是双指针遍历 哨兵节点哑节点双指针同时遍历两个有序链表每次比较两个指针指向节点的值将较小的节点接入新链表哨兵节点创建一个临时虚拟节点避免处理头节点为空的边界情况让代码更简洁拼接剩余节点当其中一个链表遍历完毕后直接将另一个链表的剩余部分接到结果链表尾部。整个过程时间复杂度 O (nm)n、m 为两个链表长度每个节点仅遍历一次空间复杂度 O (1)仅使用常数个临时指针。完整代码解析我直接给出最优解代码逐行讲解每一步的作用cpp运行/** * 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 temp; // 1. 哨兵节点哑节点不存储实际数据仅用于简化头节点处理 ListNode* cur temp;// 2. 工作指针始终指向结果链表的最后一个节点 // 3. 同时遍历两个链表直到其中一个遍历完毕 while (list1 list2) { // 比较节点值将较小的节点接到结果链表尾部 if(list1-val list2-val) { cur-next list1; list1 list1-next; // 移动原链表指针 } else { cur-next list2; list2 list2-next; } cur cur-next; // 移动工作指针始终指向新链表尾部 } // 4. 拼接剩余节点一个链表空了直接接另一个的剩余部分 cur-next list1 ? list1 : list2; // 5. 哨兵节点的next就是最终合并后的链表头节点 return temp.next; } };核心知识点详解哨兵节点temp作用解决「新链表头节点为空」的边界问题不用单独判断第一个节点该选谁最终返回temp.next就是合并后链表的真实头节点。工作指针cur始终跟踪结果链表的末尾方便后续节点直接拼接不用每次遍历找尾部。循环逻辑只有list1和list2都不为空时才进入循环每次取较小值节点接入保证新链表始终有序。剩余节点拼接因为两个原链表都是有序的剩余部分一定是递增的直接拼接即可无需再排序。代码运行演示以list1[1,2,4]、list2[1,3,4]为例初始temp - nullcurtemplist11list21第一次比较11取 list2temp-1-3-4cur1list23第二次比较13取 list1temp-1-1-2-4cur1list12第三次比较23取 list1temp-1-1-2-4cur2list14第四次比较43取 list2temp-1-1-2-3-4cur3list24第五次比较44取 list2temp-1-1-2-3-4-4cur4list2null退出循环拼接 list1 剩余节点已空最终返回temp.next。为什么推荐这个写法极简高效无冗余代码时间 / 空间复杂度均为最优无边界问题哨兵节点完美处理空链表、单节点链表等特殊情况易读易写逻辑清晰面试手写代码几乎不会出错。总结合并两个有序链表是链表基础操作核心掌握两点✅双指针遍历比较取值✅哨兵节点简化边界处理这个解法是面试高频标准答案吃透它链表基础操作就稳了