day132—链表—K个一组翻转链表（LeetCode-25）
题目描述
给你链表的头节点head，每k个节点一组进行翻转，请你返回修改后的链表。
k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3输出：[3,2,1,4,5]
提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
解决方案：
这段代码的核心功能是以 k 个节点为一组反转单链表（若最后剩余节点不足 k 个则保持原有顺序），比如链表 1→2→3→4→5、k=2 时，反转后为 2→1→4→3→5；k=3 时为 3→2→1→4→5，采用「虚拟头节点 + 分组迭代反转」实现，时间复杂度O(n)、空间复杂度O(1)，是该问题的经典最优解法。
核心逻辑
代码先统计链表长度确定可反转的组数，再逐组反转并重新拼接，核心是复用区间反转链表的逻辑，同时通过虚拟头节点简化边界处理：
- 初始化与长度统计：创建虚拟头节点
dx指向原链表头，先遍历链表统计总长度len，用于判断剩余节点是否够一组； - 分组反转循环：只要剩余节点数 ≥ k，就对当前组进行反转：
- 用
pre/cur/nxt三个指针，迭代反转当前 k 个节点（逻辑与区间反转一致）； - 反转完成后，将当前组的尾节点（原组头）指向组后第一个节点
cur，再将组前驱p0指向组新头pre； - 更新
p0为当前组的尾节点（作为下一组的前驱），并减少剩余长度len -= k；
- 用
- 返回结果：最终返回虚拟头节点的
next，即反转后链表的头节点。
总结
- 核心思路：先统计长度确定分组数，再逐组复用区间反转逻辑，用虚拟头节点和前驱指针
p0处理每组的首尾连接； - 关键操作：每组反转后
p0->next->next = cur、p0->next = pre、p0 = nxt是保证链表连续的核心，避免分组反转后断裂； - 效率特点：一次遍历统计长度 + 一次遍历分组反转，整体时间
O(n)、空间O(1)，是 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) { ListNode dx(0,head); ListNode* p0=&dx; int len=0; ListNode* tmp=head; while(tmp){ len+=1; tmp=tmp->next; }//求长度 ListNode* nxt=nullptr; ListNode* pre=nullptr; ListNode* cur=p0->next;//反转的起始节点：p0->next while(len>=k){ len-=k; //开始反转 for(int i=0;i<k;i++){ nxt=cur->next; cur->next=pre; pre=cur; cur=nxt; } //反转结束，开始更新下一次反转条件 nxt=p0->next; p0->next->next=cur; p0->next=pre; p0=nxt; } return dx.next; } };