链表Linked List是数据结构中最基础、最高频也是最考验指针操作功底的题型。它不像数组那样在内存中连续存储而是通过指针将零散的内存块串联起来。链表的本质与优缺点1. 物理结构链表由一个个“节点Node”组成每个节点包含两部分数据域val存储数据。指针域next存储下一个节点的内存地址。在 C 中通常定义为struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} };2. 与数组Array的核心对比优点增删极快。只要知道前驱节点插入或删除节点只需要改变指针指向时间复杂度 O(1)。且不需要连续内存内存利用率高。缺点查询极慢。不能像数组那样通过下标 O(1) 随机访问。要访问第 K 个节点必须从头遍历时间复杂度 O(K)。算法题的启示正因为链表“查慢增删快”链表题的考点几乎全部集中在“如何在不破坏链表结构的前提下高效地遍历和重新连接指针”。题目一两数相加/** * 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* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* cur1 l1; ListNode* cur2 l2; ListNode* newhead new ListNode(0); ListNode* prev newhead; int t 0; while (cur1 || cur2 || t) { if (cur1 ! nullptr) { t cur1-val; cur1 cur1-next; } if (cur2 ! nullptr) { t cur2-val; cur2 cur2-next; } prev-next new ListNode(t % 10); prev prev-next; t / 10; } prev newhead-next; delete newhead; return prev; } };算法思想模拟竖式加法 遍历链表这道题本质上是小学数学的加法从最低位开始相加逢十进一。因为链表是逆序存储的个位在头节点正好符合我们从低位到高位的计算顺序。我们只需遍历两个链表逐位相加并处理进位即可。逐行代码逻辑ListNode* cur1 l1; ListNode* cur2 l2;分别指向两个链表的头部用于遍历。ListNode* newhead new ListNode(0);创建一个虚拟头节点值为0。ListNode* prev newhead;prev作为尾指针始终指向新链表的最后一个节点。int t 0;t代表当前位的和以及进位。while(cur1 || cur2 || t)循环条件很关键只要两个链表还有节点或者进位t不为0就继续循环。t cur1-val;累加l1当前节点的值。t cur2-val;累加l2当前节点的值。prev-next new ListNode(t % 10);取t的个位数创建新节点并接到结果链表末尾。prev prev-next;尾指针后移。t / 10;t除以10得到进位用于下一轮循环。prev newhead-next; delete newhead; return prev;获取真正的头节点释放虚拟头节点返回结果。题目二两两交换链表中的节点/** * 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* swapPairs(ListNode* head) { if(head nullptr || head-next nullptr) return head; ListNode* cur1 head; ListNode* cur2 head-next; ListNode* newHead new ListNode(0); newHead-next head; ListNode* prev newHead; while(cur1cur2) { prev-nextcur2; cur1-nextcur2-next; cur2-nextcur1; prevcur1; cur1cur1-next; if(cur1) { cur2 cur1-next; } else { cur2 nullptr; } } ListNode* res newHead-next; delete newHead; return res; } };算法思想指针交换 虚拟头节点我们需要遍历链表每次处理两个相邻节点。核心操作是改变三个指针的指向上一组的尾节点、当前组的第一个节点、当前组的第二个节点。由于头节点也可能被交换使用虚拟头节点可以统一处理。逐行代码逻辑if(head nullptr || head-next nullptr) return head;处理边界情况。空链表或只有一个节点无需交换直接返回。ListNode* cur1 head; ListNode* cur2 head-next;初始化当前要处理的两个节点。ListNode* newHead new ListNode(0); newHead-next head;创建虚拟头节点并指向原头节点。while(cur2)循环条件。当cur2存在时说明至少有两个节点可以交换。cur1-next cur2-next;第1步将cur1指向cur2的下一个节点即让cur1指向下一组的开头。cur2-next cur1;第2步将cur2指向cur1完成交换。cur1 cur1-next; cur2 cur1-next;第3步更新指针准备处理下一组。题目三重排链表/** * 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: void reorderList(ListNode* head) { if (head nullptr || head-next nullptr || head-next-next nullptr) return; } ListNode *slow head, *fast head; while(fast fast-next) { slow slow-next; fast fast-next-next; } ListNode* head2 new ListNode(0); ListNode* curslow-next; slow-nextnullptr; while(cur) { ListNode* next cur-next; cur-nexthead2-next; head2-nextcur; curnext; } ListNode* ret new ListNode(0); ListNode* prev ret; ListNode* cur1 head, *cur2 head2-next; while(cur1) { prev-nextcur1; cur1cur1-next; prevprev-next; if(cur2) { prev-nextcur2; prevprev-next; cur2cur2-next; } } delete head2; return ret; };算法思想快慢指针找中点 头插法反转后半段 合并两个链表这是一道综合性很强的题目分为三个清晰的步骤用快慢指针找到链表中点。将中点后的后半部分链表用头插法进行反转。将前半部分与反转后的后半部分交替合并。逐行代码逻辑if (head nullptr || head-next nullptr || head-next-next nullptr) return;处理边界。节点数少于3时重排后顺序不变。ListNode *slow head, *fast head;初始化快慢指针。while (fast fast-next)快指针每次走两步慢指针每次走一步。循环结束时slow位于中间节点。ListNode* head2 new ListNode(0);为反转后半段创建虚拟头节点。ListNode* cur slow-next;cur指向后半段的第一个节点。slow-next nullptr;关键步骤断开前后两半使前一半成为独立链表。while(cur) { ... }头插法反转链表。next cur-next;(保存下一个)cur-next head2-next;(指向新头部)head2-next cur;(新头接管)cur next;(后移)。ListNode* ret new ListNode(0); ListNode* prev ret;创建最终结果链表的虚拟头节点和尾指针。ListNode* cur1 head, *cur2 head2-next;分别指向前半段和反转后的后半段头部。while(cur1)循环合并。因为前半段长度一定大于等于后半段所以以cur1为主循环条件。prev-next cur1; cur1 cur1-next; prev prev-next;先放第一个链表的节点。if(cur2) { prev-next cur2; cur2 cur2-next; prev prev-next; }再放第二个链表的节点如果有的话。结尾释放虚拟头节点delete ret;返回ret-next。题目四合并K个升序链表/** * 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 { struct cmp { bool operator()(const ListNode* l1, const ListNode* l2) { return l1-val l2-val; } }; public: ListNode* mergeKLists(vectorListNode* lists) { priority_queueListNode*, vectorListNode*, cmp heap; for (auto l : lists) { if (l) heap.push(l); } ListNode* ret new ListNode(0); ListNode* prev ret; while (!heap.empty()) { ListNode* t heap.top(); heap.pop(); prev-next t; prev t; if (t-next) heap.push(t-next); } prev ret-next; delete ret; return prev; } };算法思想优先队列最小堆面对 K 个有序链表每次只需要从 K 个链表的“当前头部”中选出最小的那一个接到结果链表上。这个过程正好可以用“最小堆”来实现堆顶永远是当前的最小值。逐行代码逻辑struct cmp { bool operator()(const ListNode* l1, const ListNode* l2) { return l1-val l2-val; } };自定义比较器。在优先队列中返回true表示l1优先级低于l2。这里用使得值小的优先级高从而构造小根堆。priority_queueListNode*, vectorListNode*, cmp heap;声明一个存放ListNode*的小根堆。for(auto l : lists) { if(l) heap.push(l); }将所有链表的头节点放入堆中。注意必须判断if(l)因为lists中可能包含空链表。ListNode* ret new ListNode(0); ListNode* prev ret;创建虚拟头节点和尾指针。while(!heap.empty())只要堆非空就继续合并。ListNode* t heap.top(); heap.pop();取出堆顶节点全局最小值并从堆中移除。prev-next t; prev t;将取出的节点连接到结果链表末尾。if(t-next) heap.push(t-next);关键步骤如果取出的节点后面还有节点必须将它的下一个节点入堆参与后续的比较。结尾释放虚拟头节点delete ret;返回ret-next。题目五K个一组反转链表/** * 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* reverseKGroup(ListNode* head, int k) { // 1. 计算链表的总长度 int n 0; ListNode* cur head; while(cur) { cur cur-next; n; } n / k; // 计算出一共需要反转多少组 // 2. 初始化指针 ListNode* newHead new ListNode(0); // 总虚拟头节点用于统一处理头部 ListNode* prev newHead; // 核心指针 始终指向上一组反转后的尾节点 cur head; // 重新指向原链表头部准备开始反转 // 3. 外层循环固定循环 n 次n 是总组数 for(int i 0; i n; i) { ListNode* tmp cur; // 【极其关键】记录这一组反转前的第一个节点 // 4. 内层循环对每一组进行长度为 k 的头插法反转 for(int j 0; j k; j) { ListNode* next cur-next; // 保命步先存下一个节点防断链 cur-next prev-next; // 断旧连新当前节点指向 prev 后面的节点 prev-next cur; // 新头接管prev 接管当前节点 cur next; // 指针推进cur 后移 } // 5. 一组反转完毕后的收尾工作 prev tmp; // 精髓所在 将 prev 更新为这一组原来的头节点即现在的尾节点 } // 6. 拼接不需要反转的剩余部分 prev-next cur; // 7. 返回最终结果并释放内存 cur newHead-next; delete newHead; return cur; } };算法思想分组头插法 宏观指针拼接这道题的核心难点在于如何把反转好的局部链表重新天衣无缝地拼回原链表中先遍历一遍算出链表总长度n。计算需要反转的组数n / k。这就意味着剩下的n % k个节点完全不需要处理直接留在原地即可。外层for循环次数固定不需要在循环内部去判断“剩余节点够不够 K 个”。外层循环控制组数内层循环执行“头插法反转”。每次反转 K 个节点并且利用一个prev指针记录上一组的尾部用于承接下一组。这五道题几乎覆盖了链表操作的所有核心场景遍历、增删、反转、合并、分组。核心重难点算法思想层面1. 虚拟头节点—— 链表的“万能钥匙”在这五道题中几乎每一题都用到了虚拟头节点两数相加、两两交换、重排链表、合并K个、K个一组翻转。作用将“头节点”的特殊情况普通化。如果没有它你需要在每个操作前判断“我是不是在操作第一个节点”代码会变得极其臃肿。重难点虚拟头节点不仅用于“构建结果链表”还用于“作为前置节点辅助翻转”如K个一组中的prev。口诀只要涉及头节点可能改变的链表操作先建 虚拟头节点。2. 指针的“保存与推进” —— 链表的“命脉”链表不像数组可以通过下标随机访问一旦指针断开后续节点就永远丢失了。重难点在改变任何一个节点的next指向之前必须先保存它的原始后继节点。实战体现反转链表中的next cur-next;先存后断。K个一组翻转中的tmp cur;保存本组开头反转后会变成尾部。合并链表中的cur1 cur1-next;推进指针。3. 快慢指针 —— 找中点/判环的神器重难点slow走一步fast走两步。循环条件while(fast fast-next)决定了slow最终停在哪里。实战体现在“重排链表”中正是利用快慢指针找到中点才得以将链表一分为二。要注意区分节点总数的奇偶性对slow位置的影响。深度易错点代码实现层面1. 空指针解引用这是链表题最致命的错误通常发生在以下三个场景遍历时越界while(cur-next)没判断cur是否为空。正确写法while(cur cur-next)。累加值时越界如“两数相加”中t cur1-val;如果cur1已经是nullptr直接崩溃。必须在前面加if(cur1)。推进指针时越界如“两两交换”中如果cur1已经变成nullptr再去cur2 cur1-next;就会崩溃。先更新cur2再更新cur1是安全的顺序。2. 指针丢失与断链逻辑错误反转时的断链执行cur-next prev;之前如果没有保存cur-next后面的链表就全丢了。合并时的断链合并两个链表时如果先移动了cur1再想用cur1去接后面的节点就会发现cur1已经指向别处了。必须先用prev-next把节点接上再移动cur1。3. 循环终止条件写错死循环或漏节点合并K个优先队列版while(!heap.empty())没问题但循环内部如果忘记if(t-next) heap.push(t-next);那么取出的节点后面的所有节点都会丢失。重排链表合并时如果用while(cur1 cur2)奇数个节点时前半段最后一个节点会被遗漏。以较长的链表作为循环条件while(cur1)才是安全的。K个一组翻转如果内层循环写成while(cur)而不是for(int j 0; j k; j)那么当剩余节点不足 K 个时也会被错误地翻转。4. 内存泄漏在 C 中new出来的虚拟头节点在返回结果前必须delete。如“重排链表”中的delete ret;“两数相加”中的delete newhead;。进阶技巧在“合并K个分治版”中使用栈上局部变量ListNode head;替代new ListNode(0)既不需要delete效率也更高。5. 虚拟头节点忘记断开原连接在“重排链表”中找到中点后必须执行slow-next nullptr;。如果不切断前半段的尾节点仍然指向后半段合并时就会形成环导致程序死循环。思维框架面对任何链表题画图不要空想在纸上画出指针的初始状态和目标状态。设虚拟头节点除非明确知道头节点不会改变如纯粹的遍历否则一律先建dummy。定循环条件明确循环结束的边界是nullptr还是某个特定节点注意的短路特性。先存后改在修改任何next指针前先确认自己已经保存了所有必要的后继节点。收尾检查最后返回的是不是dummy-next有没有节点被遗漏尤其是尾部有没有动态内存没有释放 算法 --链表
链表Linked List是数据结构中最基础、最高频也是最考验指针操作功底的题型。它不像数组那样在内存中连续存储而是通过指针将零散的内存块串联起来。链表的本质与优缺点1. 物理结构链表由一个个“节点Node”组成每个节点包含两部分数据域val存储数据。指针域next存储下一个节点的内存地址。在 C 中通常定义为struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} };2. 与数组Array的核心对比优点增删极快。只要知道前驱节点插入或删除节点只需要改变指针指向时间复杂度 O(1)。且不需要连续内存内存利用率高。缺点查询极慢。不能像数组那样通过下标 O(1) 随机访问。要访问第 K 个节点必须从头遍历时间复杂度 O(K)。算法题的启示正因为链表“查慢增删快”链表题的考点几乎全部集中在“如何在不破坏链表结构的前提下高效地遍历和重新连接指针”。题目一两数相加/** * 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* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* cur1 l1; ListNode* cur2 l2; ListNode* newhead new ListNode(0); ListNode* prev newhead; int t 0; while (cur1 || cur2 || t) { if (cur1 ! nullptr) { t cur1-val; cur1 cur1-next; } if (cur2 ! nullptr) { t cur2-val; cur2 cur2-next; } prev-next new ListNode(t % 10); prev prev-next; t / 10; } prev newhead-next; delete newhead; return prev; } };算法思想模拟竖式加法 遍历链表这道题本质上是小学数学的加法从最低位开始相加逢十进一。因为链表是逆序存储的个位在头节点正好符合我们从低位到高位的计算顺序。我们只需遍历两个链表逐位相加并处理进位即可。逐行代码逻辑ListNode* cur1 l1; ListNode* cur2 l2;分别指向两个链表的头部用于遍历。ListNode* newhead new ListNode(0);创建一个虚拟头节点值为0。ListNode* prev newhead;prev作为尾指针始终指向新链表的最后一个节点。int t 0;t代表当前位的和以及进位。while(cur1 || cur2 || t)循环条件很关键只要两个链表还有节点或者进位t不为0就继续循环。t cur1-val;累加l1当前节点的值。t cur2-val;累加l2当前节点的值。prev-next new ListNode(t % 10);取t的个位数创建新节点并接到结果链表末尾。prev prev-next;尾指针后移。t / 10;t除以10得到进位用于下一轮循环。prev newhead-next; delete newhead; return prev;获取真正的头节点释放虚拟头节点返回结果。题目二两两交换链表中的节点/** * 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* swapPairs(ListNode* head) { if(head nullptr || head-next nullptr) return head; ListNode* cur1 head; ListNode* cur2 head-next; ListNode* newHead new ListNode(0); newHead-next head; ListNode* prev newHead; while(cur1cur2) { prev-nextcur2; cur1-nextcur2-next; cur2-nextcur1; prevcur1; cur1cur1-next; if(cur1) { cur2 cur1-next; } else { cur2 nullptr; } } ListNode* res newHead-next; delete newHead; return res; } };算法思想指针交换 虚拟头节点我们需要遍历链表每次处理两个相邻节点。核心操作是改变三个指针的指向上一组的尾节点、当前组的第一个节点、当前组的第二个节点。由于头节点也可能被交换使用虚拟头节点可以统一处理。逐行代码逻辑if(head nullptr || head-next nullptr) return head;处理边界情况。空链表或只有一个节点无需交换直接返回。ListNode* cur1 head; ListNode* cur2 head-next;初始化当前要处理的两个节点。ListNode* newHead new ListNode(0); newHead-next head;创建虚拟头节点并指向原头节点。while(cur2)循环条件。当cur2存在时说明至少有两个节点可以交换。cur1-next cur2-next;第1步将cur1指向cur2的下一个节点即让cur1指向下一组的开头。cur2-next cur1;第2步将cur2指向cur1完成交换。cur1 cur1-next; cur2 cur1-next;第3步更新指针准备处理下一组。题目三重排链表/** * 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: void reorderList(ListNode* head) { if (head nullptr || head-next nullptr || head-next-next nullptr) return; } ListNode *slow head, *fast head; while(fast fast-next) { slow slow-next; fast fast-next-next; } ListNode* head2 new ListNode(0); ListNode* curslow-next; slow-nextnullptr; while(cur) { ListNode* next cur-next; cur-nexthead2-next; head2-nextcur; curnext; } ListNode* ret new ListNode(0); ListNode* prev ret; ListNode* cur1 head, *cur2 head2-next; while(cur1) { prev-nextcur1; cur1cur1-next; prevprev-next; if(cur2) { prev-nextcur2; prevprev-next; cur2cur2-next; } } delete head2; return ret; };算法思想快慢指针找中点 头插法反转后半段 合并两个链表这是一道综合性很强的题目分为三个清晰的步骤用快慢指针找到链表中点。将中点后的后半部分链表用头插法进行反转。将前半部分与反转后的后半部分交替合并。逐行代码逻辑if (head nullptr || head-next nullptr || head-next-next nullptr) return;处理边界。节点数少于3时重排后顺序不变。ListNode *slow head, *fast head;初始化快慢指针。while (fast fast-next)快指针每次走两步慢指针每次走一步。循环结束时slow位于中间节点。ListNode* head2 new ListNode(0);为反转后半段创建虚拟头节点。ListNode* cur slow-next;cur指向后半段的第一个节点。slow-next nullptr;关键步骤断开前后两半使前一半成为独立链表。while(cur) { ... }头插法反转链表。next cur-next;(保存下一个)cur-next head2-next;(指向新头部)head2-next cur;(新头接管)cur next;(后移)。ListNode* ret new ListNode(0); ListNode* prev ret;创建最终结果链表的虚拟头节点和尾指针。ListNode* cur1 head, *cur2 head2-next;分别指向前半段和反转后的后半段头部。while(cur1)循环合并。因为前半段长度一定大于等于后半段所以以cur1为主循环条件。prev-next cur1; cur1 cur1-next; prev prev-next;先放第一个链表的节点。if(cur2) { prev-next cur2; cur2 cur2-next; prev prev-next; }再放第二个链表的节点如果有的话。结尾释放虚拟头节点delete ret;返回ret-next。题目四合并K个升序链表/** * 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 { struct cmp { bool operator()(const ListNode* l1, const ListNode* l2) { return l1-val l2-val; } }; public: ListNode* mergeKLists(vectorListNode* lists) { priority_queueListNode*, vectorListNode*, cmp heap; for (auto l : lists) { if (l) heap.push(l); } ListNode* ret new ListNode(0); ListNode* prev ret; while (!heap.empty()) { ListNode* t heap.top(); heap.pop(); prev-next t; prev t; if (t-next) heap.push(t-next); } prev ret-next; delete ret; return prev; } };算法思想优先队列最小堆面对 K 个有序链表每次只需要从 K 个链表的“当前头部”中选出最小的那一个接到结果链表上。这个过程正好可以用“最小堆”来实现堆顶永远是当前的最小值。逐行代码逻辑struct cmp { bool operator()(const ListNode* l1, const ListNode* l2) { return l1-val l2-val; } };自定义比较器。在优先队列中返回true表示l1优先级低于l2。这里用使得值小的优先级高从而构造小根堆。priority_queueListNode*, vectorListNode*, cmp heap;声明一个存放ListNode*的小根堆。for(auto l : lists) { if(l) heap.push(l); }将所有链表的头节点放入堆中。注意必须判断if(l)因为lists中可能包含空链表。ListNode* ret new ListNode(0); ListNode* prev ret;创建虚拟头节点和尾指针。while(!heap.empty())只要堆非空就继续合并。ListNode* t heap.top(); heap.pop();取出堆顶节点全局最小值并从堆中移除。prev-next t; prev t;将取出的节点连接到结果链表末尾。if(t-next) heap.push(t-next);关键步骤如果取出的节点后面还有节点必须将它的下一个节点入堆参与后续的比较。结尾释放虚拟头节点delete ret;返回ret-next。题目五K个一组反转链表/** * 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* reverseKGroup(ListNode* head, int k) { // 1. 计算链表的总长度 int n 0; ListNode* cur head; while(cur) { cur cur-next; n; } n / k; // 计算出一共需要反转多少组 // 2. 初始化指针 ListNode* newHead new ListNode(0); // 总虚拟头节点用于统一处理头部 ListNode* prev newHead; // 核心指针 始终指向上一组反转后的尾节点 cur head; // 重新指向原链表头部准备开始反转 // 3. 外层循环固定循环 n 次n 是总组数 for(int i 0; i n; i) { ListNode* tmp cur; // 【极其关键】记录这一组反转前的第一个节点 // 4. 内层循环对每一组进行长度为 k 的头插法反转 for(int j 0; j k; j) { ListNode* next cur-next; // 保命步先存下一个节点防断链 cur-next prev-next; // 断旧连新当前节点指向 prev 后面的节点 prev-next cur; // 新头接管prev 接管当前节点 cur next; // 指针推进cur 后移 } // 5. 一组反转完毕后的收尾工作 prev tmp; // 精髓所在 将 prev 更新为这一组原来的头节点即现在的尾节点 } // 6. 拼接不需要反转的剩余部分 prev-next cur; // 7. 返回最终结果并释放内存 cur newHead-next; delete newHead; return cur; } };算法思想分组头插法 宏观指针拼接这道题的核心难点在于如何把反转好的局部链表重新天衣无缝地拼回原链表中先遍历一遍算出链表总长度n。计算需要反转的组数n / k。这就意味着剩下的n % k个节点完全不需要处理直接留在原地即可。外层for循环次数固定不需要在循环内部去判断“剩余节点够不够 K 个”。外层循环控制组数内层循环执行“头插法反转”。每次反转 K 个节点并且利用一个prev指针记录上一组的尾部用于承接下一组。这五道题几乎覆盖了链表操作的所有核心场景遍历、增删、反转、合并、分组。核心重难点算法思想层面1. 虚拟头节点—— 链表的“万能钥匙”在这五道题中几乎每一题都用到了虚拟头节点两数相加、两两交换、重排链表、合并K个、K个一组翻转。作用将“头节点”的特殊情况普通化。如果没有它你需要在每个操作前判断“我是不是在操作第一个节点”代码会变得极其臃肿。重难点虚拟头节点不仅用于“构建结果链表”还用于“作为前置节点辅助翻转”如K个一组中的prev。口诀只要涉及头节点可能改变的链表操作先建 虚拟头节点。2. 指针的“保存与推进” —— 链表的“命脉”链表不像数组可以通过下标随机访问一旦指针断开后续节点就永远丢失了。重难点在改变任何一个节点的next指向之前必须先保存它的原始后继节点。实战体现反转链表中的next cur-next;先存后断。K个一组翻转中的tmp cur;保存本组开头反转后会变成尾部。合并链表中的cur1 cur1-next;推进指针。3. 快慢指针 —— 找中点/判环的神器重难点slow走一步fast走两步。循环条件while(fast fast-next)决定了slow最终停在哪里。实战体现在“重排链表”中正是利用快慢指针找到中点才得以将链表一分为二。要注意区分节点总数的奇偶性对slow位置的影响。深度易错点代码实现层面1. 空指针解引用这是链表题最致命的错误通常发生在以下三个场景遍历时越界while(cur-next)没判断cur是否为空。正确写法while(cur cur-next)。累加值时越界如“两数相加”中t cur1-val;如果cur1已经是nullptr直接崩溃。必须在前面加if(cur1)。推进指针时越界如“两两交换”中如果cur1已经变成nullptr再去cur2 cur1-next;就会崩溃。先更新cur2再更新cur1是安全的顺序。2. 指针丢失与断链逻辑错误反转时的断链执行cur-next prev;之前如果没有保存cur-next后面的链表就全丢了。合并时的断链合并两个链表时如果先移动了cur1再想用cur1去接后面的节点就会发现cur1已经指向别处了。必须先用prev-next把节点接上再移动cur1。3. 循环终止条件写错死循环或漏节点合并K个优先队列版while(!heap.empty())没问题但循环内部如果忘记if(t-next) heap.push(t-next);那么取出的节点后面的所有节点都会丢失。重排链表合并时如果用while(cur1 cur2)奇数个节点时前半段最后一个节点会被遗漏。以较长的链表作为循环条件while(cur1)才是安全的。K个一组翻转如果内层循环写成while(cur)而不是for(int j 0; j k; j)那么当剩余节点不足 K 个时也会被错误地翻转。4. 内存泄漏在 C 中new出来的虚拟头节点在返回结果前必须delete。如“重排链表”中的delete ret;“两数相加”中的delete newhead;。进阶技巧在“合并K个分治版”中使用栈上局部变量ListNode head;替代new ListNode(0)既不需要delete效率也更高。5. 虚拟头节点忘记断开原连接在“重排链表”中找到中点后必须执行slow-next nullptr;。如果不切断前半段的尾节点仍然指向后半段合并时就会形成环导致程序死循环。思维框架面对任何链表题画图不要空想在纸上画出指针的初始状态和目标状态。设虚拟头节点除非明确知道头节点不会改变如纯粹的遍历否则一律先建dummy。定循环条件明确循环结束的边界是nullptr还是某个特定节点注意的短路特性。先存后改在修改任何next指针前先确认自己已经保存了所有必要的后继节点。收尾检查最后返回的是不是dummy-next有没有节点被遗漏尤其是尾部有没有动态内存没有释放 
