文章目录一、 核心原理链表指针操作的本质二、 两两交换链表中的节点 (Medium)2.1 题目描述2.2 深度拆解画图画图画图2.3 C 代码实战三、 重排链表 (Medium)3.1 题目描述3.2 深度拆解三步分解各个击破3.3 C 代码实战四、 合并 K 个升序链表 (Hard)4.1 题目描述4.2 深度拆解两种思路的对比4.3 C 代码实战解法一小根堆4.4 C 代码实战解法二分治递归五、 K 个一组翻转链表 (Hard)5.1 题目描述5.2 深度拆解分组 头插法5.3 C 代码实战六、 总结与避坑一、 核心原理链表指针操作的本质底层逻辑链表题的核心永远是指针的重定向。不同于数组可以随机访问链表的每一次操作本质上都是在修改next指针的指向。哨兵节点虚拟头节点new ListNode(0)是链表题的万能润滑剂。它统一了头节点也需要被修改的边界情况让代码逻辑更整洁。画图是第一生产力链表指针绕来绕去脑子里很难追踪。强烈建议动手画出每一步的指针变化再翻译成代码否则极易出现断链或空指针。操作顺序至关重要在重新连接指针时顺序一旦错误就会丢失对后续节点的引用导致链表断裂。每次操作前务必确认我还拿着我需要的节点吗链表题通用模板虚拟头节点ListNode* dummy new ListNode(0); dummy-next head;多指针协作prev、cur、next、nnext各司其职提前保存好待会儿还要用的节点。善用头插法逆序一段链表时头插法是最简洁的实现方式。二、 两两交换链表中的节点 (Medium)2.1 题目描述链接24. 两两交换链表中的节点给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。必须实际交换节点不能只修改节点内部的值。2.2 深度拆解画图画图画图画图画图画图重要的事情说三遍四指针协作每次循环需要同时掌控prev、cur、next、nnext四个指针分别对应交换区间的前驱、第一个节点、第二个节点、后继。交换三步走prev-next next前驱接到第二个节点next-next cur第二个节点反指第一个cur-next nnext第一个节点接到后继指针后移的顺序prev cur必须在cur nnext之前因为 cur 此时已经是交换后的尾节点是下一轮的 prev。2.3 C 代码实战/** * 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) {} * }; */classSolution{public:ListNode*swapPairs(ListNode*head){if(headnullptr||head-nextnullptr)returnhead;// 1. 虚拟头节点统一边界处理ListNode*newHeadnewListNode(0);newHead-nexthead;ListNode*prevnewHead,*curprev-next,*nextcur-next,*nnextnext-next;while(curnext){// 2. 交换节点修改三条指针prev-nextnext;next-nextcur;cur-nextnnext;// 3. 后移指针注意顺序prevcur;// prev 先移到 cur此时 cur 是交换后的尾节点curnnext;if(cur)nextcur-next;if(next)nnextnext-next;}curnewHead-next;deletenewHead;returncur;}};三、 重排链表 (Medium)3.1 题目描述链接143. 重排链表给定单链表L(0) → L(1) → … → L(n)将其重排为L(0) → L(n) → L(1) → L(n-1) → L(2) → L(n-2) → …不能只改变节点值必须实际交换节点。3.2 深度拆解三步分解各个击破画图画图画图重要的事情说三遍这道题直接模拟很难但拆成三个子问题后每一步都是经典操作第一步找中间节点—— 快慢双指针。fast每次走两步slow每次走一步fast到头时slow就在中间。务必画图确认slow的落点奇偶长度下落点不同。第二步逆序后半段—— 头插法。将slow-next之后的所有节点头插到一个新的虚拟头节点后自然得到逆序链表。注意要将前后两段断开slow-next nullptr。第三步合并两条链表—— 双指针交替拼接。cur1遍历前半段cur2遍历后半段交替接到结果链表上。3.3 C 代码实战classSolution{public:voidreorderList(ListNode*head){if(headnullptr||head-nextnullptr||head-next-nextnullptr)return;// 1. 找到链表的中间节点 - 快慢双指针一定要画图考虑 slow 的落点在哪里ListNode*slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}// 2. 把 slow 后面的部分给逆序 - 头插法ListNode*head2newListNode(0);ListNode*curslow-next;slow-nextnullptr;// 注意把两个链表给断开while(cur){ListNode*nextcur-next;cur-nexthead2-next;head2-nextcur;curnext;}// 3. 合并两个链表 - 双指针交替拼接ListNode*retnewListNode(0);ListNode*prevret;ListNode*cur1head,*cur2head2-next;while(cur1){// 先放第一个链表prev-nextcur1;cur1cur1-next;prevprev-next;// 再放第二个链表if(cur2){prev-nextcur2;prevprev-next;cur2cur2-next;}}deletehead2;deleteret;}};四、 合并 K 个升序链表 (Hard)4.1 题目描述链接23. 合并 K 个升序链表给你一个链表数组每个链表都已按升序排列请将所有链表合并到一个升序链表中并返回。4.2 深度拆解两种思路的对比解法一小根堆合并两个有序链表时双指针每次选较小的节点。推广到K KK个链表我们需要每次快速找到K KK个头节点中最小的那个这正是小根堆的用武之地。将所有头节点入堆每次弹出最小节点接到答案链表再将该节点的next压入堆时间复杂度O ( N log ⁡ K ) O(N \log K)O(NlogK)。解法二分治/递归逐一合并时答案链表越来越长后面每个小链表的元素都要参与大量无效比较。分治思路让长度相近的链表两两合并类比归并排序总比较次数从O ( N K ) O(NK)O(NK)优化到O ( N log ⁡ K ) O(N \log K)O(NlogK)常数更小实践中更快。4.3 C 代码实战解法一小根堆classSolution{structcmp{booloperator()(constListNode*l1,constListNode*l2){returnl1-vall2-val;// 小根堆}};public:ListNode*mergeKLists(vectorListNode*lists){// 1. 创建小根堆让所有头节点入堆priority_queueListNode*,vectorListNode*,cmpheap;for(autol:lists)if(l)heap.push(l);// 2. 合并 K 个有序链表ListNode*retnewListNode(0);ListNode*prevret;while(!heap.empty()){ListNode*theap.top();heap.pop();prev-nextt;prevt;if(t-next)heap.push(t-next);// 弹出后将其 next 补入堆}prevret-next;deleteret;returnprev;}};4.4 C 代码实战解法二分治递归classSolution{public:ListNode*mergeKLists(vectorListNode*lists){returnmerge(lists,0,lists.size()-1);}ListNode*merge(vectorListNode*lists,intleft,intright){if(leftright)returnnullptr;if(leftright)returnlists[left];// 1. 平分数组让长度相近的链表合并intmidleftright1;ListNode*l1merge(lists,left,mid);ListNode*l2merge(lists,mid1,right);// 2. 合并两个有序链表returnmergeTwoList(l1,l2);}ListNode*mergeTwoList(ListNode*l1,ListNode*l2){if(l1nullptr)returnl2;if(l2nullptr)returnl1;ListNode head;ListNode*cur1l1,*cur2l2,*prevhead;head.nextnullptr;while(cur1cur2){if(cur1-valcur2-val){prevprev-nextcur1;cur1cur1-next;}else{prevprev-nextcur2;cur2cur2-next;}}if(cur1)prev-nextcur1;if(cur2)prev-nextcur2;returnhead.next;}};五、 K 个一组翻转链表 (Hard)5.1 题目描述链接25. K 个一组翻转链表给你链表的头节点head每k kk个节点一组进行翻转返回修改后的链表。若剩余节点不足k kk个则保持原有顺序。5.2 深度拆解分组 头插法本题逻辑清晰难度在于细节处理分组计数先遍历链表求总长度n nn然后n ÷ k n \div kn÷k得到需要逆序的组数剩余节点直接接上即可不需要特判。组内逆序头插法对每组的k kk个节点依次将每个节点头插到prev之后。头插结束后原来的组头节点tmp自然成为了该组的组尾是下一轮的prev。关键变量tmp在头插开始前先用tmp cur记住当前组的第一个节点头插结束后它会成为组尾作为下一轮循环prev的新值。5.3 C 代码实战classSolution{public:ListNode*reverseKGroup(ListNode*head,intk){// 1. 先求出需要逆序多少组intn0;ListNode*curhead;while(cur){curcur-next;n;}n/k;// 2. 重复 n 次对长度为 k 的链表段进行头插逆序ListNode*newHeadnewListNode(0);ListNode*prevnewHead;curhead;for(inti0;in;i){ListNode*tmpcur;// 记住组头头插后它将成为组尾for(intj0;jk;j){ListNode*nextcur-next;cur-nextprev-next;prev-nextcur;curnext;}prevtmp;// 组头已变组尾作为下一轮的 prev}// 3. 把不需要翻转的剩余部分接上prev-nextcur;curnewHead-next;deletenewHead;returncur;}};六、 总结与避坑复盘链表的指针操作是模板化程度很高的技巧掌握以下规律后大部分题目都能迎刃而解。虚拟头节点是标配只要头节点可能被修改交换、合并、逆序第一步就加dummy省去大量边界判断。画图再动手指针操作在脑子里极易绕晕每道新题务必先画出节点变化图再翻译成代码。提前保存待用节点修改cur-next之前必须先用临时变量保存cur-next否则后继节点将永久丢失。头插法逆序的本质每次将cur插到prev-next的位置循环k kk次后原来从左到右的顺序自然变为从右到左。分治优于逐一合并合并K KK个链表时分治比逐一合并的实际运行时间快很多因为每条链表的节点参与比较的总次数从O ( K ) O(K)O(K)降到O ( log ⁡ K ) O(\log K)O(logK)。