hot100_K个一组翻转链表

1. 题目

给你链表的头节点 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]

2. 题解

2.1. 递归

2.1.1. 核心思想

2.1.2. 代码

/**
* 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* cur = head;
for(int i = 0; i < k; i++) {
if(cur == nullptr) return head;
cur = cur -> next;
}
ListNode* pre = nullptr;
ListNode* p = head;
for(int i = 0; i < k; i++) {
ListNode* nxt = p->next;
p->next = pre;
pre = p;
p = nxt;
}
head->next = reverseKGroup(p, k);
return pre;
}
};

2.1.3. 复杂度

时间复杂度：

O

(

n

)

O(n)

O(n)，n 是链表总节点数。 空间复杂度：

O

(

n

k

)

O(\\dfrac{n}{k})

O(kn​)。注意：递归的空间消耗来自调用栈，不是堆内存。

• 每处理 k 个节点，产生 1 层递归栈帧。
• 总递归深度：$\lfloor \frac{n}{k}\rfloor$

2.2. 模拟

2.2.1. 核心思想

2.2.2. 代码

/**
* 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* reverse(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur != nullptr) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* end = dummy;

while(end->next != nullptr) {
// 移动 end 到本组末尾，不足k个就退出
for(int i = 0; i < k && end != nullptr; i++) {
end = end->next;
}
if(end == nullptr) break; // 剩余节点不足k个
ListNode* start = pre->next; // 当前组起点
ListNode* next = end->next; // 下一组起点

end->next = nullptr; // 断开，方便reverse
pre->next = reverse(start); // 翻转本组

start->next = next; // 原来的头变成本组尾，接上后面链表
pre = start; // pre移动到本组尾部，作为下一组前驱
end = pre; // end重置，下一轮继续往后走k步
}
return dummy->next;
}
};

2.2.3. 复杂度

时间复杂度：

O

(

n

)

O(n)

O(n)，每个节点最多遍历两次 空间复杂度：

O

(

1

)

O(1)

O(1)，只使用若干指针，原地翻转

2.3. 两种算法对比

3. 25. K 个一组翻转链表 – 力扣（LeetCode）