企业官网建设流程全解析

题目描述

给你链表的头节点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 <= 5000
• 0 <= 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)，是该问题的经典最优解法。

核心逻辑

代码先统计链表长度确定可反转的组数，再逐组反转并重新拼接，核心是复用区间反转链表的逻辑，同时通过虚拟头节点简化边界处理：

1. 初始化与长度统计：创建虚拟头节点dx指向原链表头，先遍历链表统计总长度len，用于判断剩余节点是否够一组；
2. 分组反转循环：只要剩余节点数 ≥ k，就对当前组进行反转：
   • 用pre/cur/nxt三个指针，迭代反转当前 k 个节点（逻辑与区间反转一致）；
   • 反转完成后，将当前组的尾节点（原组头）指向组后第一个节点cur，再将组前驱p0指向组新头pre；
   • 更新p0为当前组的尾节点（作为下一组的前驱），并减少剩余长度len -= k；
3. 返回结果：最终返回虚拟头节点的next，即反转后链表的头节点。

总结

1. 核心思路：先统计长度确定分组数，再逐组复用区间反转逻辑，用虚拟头节点和前驱指针p0处理每组的首尾连接；
2. 关键操作：每组反转后p0->next->next = cur、p0->next = pre、p0 = nxt是保证链表连续的核心，避免分组反转后断裂；
3. 效率特点：一次遍历统计长度 + 一次遍历分组反转，整体时间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; } };