25. K 个一组翻转链表
3 min
题目
解法：头插翻转
思路
核心思想是使用头插法分组翻转链表。通过dummy节点简化头节点处理，对每组节点执行k-1次头插操作实现翻转。
正确性在于：头插法将组内第2至k个节点依次插入组前，自然形成逆序；组间通过pre指针衔接确保连接正确，且剩余不足k的组因不进入循环保持原序。
- Step 1: 计算链表长度并确定翻转组数
- Step 2: 初始化dummy节点，pre指向dummy，cur指向头节点
- Step 3: 循环组数次，每组执行k-1次头插（将cur->next移到pre后）
- Step 4: 更新pre为当前组尾节点，cur指向下一组头节点
复杂度
- 时间复杂度: ，遍历链表两次（计算长度和翻转操作），每个节点被处理常数次。
- 空间复杂度: ，仅使用dummy节点和固定数量指针。
代码
/**
* 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) {
if (!head || k == 1) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = head;
int length = 0;
while (cur) {
length++;
cur = cur->next;
}
/**
* 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) {
if (!head || k == 1) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = head;
int length = 0;
while (cur) {
length++;
cur = cur->next;
}
ListNode* pre = dummy;
cur = head;
ListNode* nex = nullptr;
// 对每 k 个节点进行一组翻转
for (int i = 0; i < length / k; i++) {
for (int j = 1; j < k; j++) {
nex = cur->next;
cur->next = nex->next;
nex->next = pre->next;
pre->next = nex;
}
pre = cur;
cur = cur->next;
}
return dummy->next;
}
};