# 25.reverse-nodes-in-k-groups-cn
## 题目地址
## 题目描述
```
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:
Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.
```
## 思路
题意是以 `k` 个nodes为一组进行翻转，返回翻转后的`linked list`.
从左往右扫描一遍`linked list`，扫描过程中，以k为单位把数组分成若干段，对每一段进行翻转。给定首尾nodes，如何对链表进行翻转。
链表的翻转过程，初始化一个为`null`的 `previous node（prev）`，然后遍历链表的同时，当前`node （curr）`的下一个（next）指向前一个`node（prev）`， 在改变当前node的指向之前，用一个临时变量记录当前node的下一个`node（curr.next)`. 即
```
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
```
举例如图：翻转整个链表 `1->2->3->4->null` -> `4->3->2->1->null`
这里是对每一组（`k个nodes`）进行翻转，
1. 先分组，用一个`count`变量记录当前节点的个数
2. 用一个`start` 变量记录当前分组的起始节点位置的前一个节点
3. 用一个`end`变量记录要翻转的最后一个节点位置
4. 翻转一组（`k个nodes`）即`(start, end) - start and end exclusively`。
5. 翻转后，`start`指向翻转后链表, 区间`（start，end）`中的最后一个节点, 返回`start` 节点。
6. 如果不需要翻转，`end` 就往后移动一个（`end=end.next`)，每一次移动，都要`count+1`.
如图所示 步骤4和5： 翻转区间链表区间`（start， end）`
举例如图，`head=[1,2,3,4,5,6,7,8], k = 3`
> **NOTE**: 一般情况下对链表的操作，都有可能会引入一个新的`dummy node`，因为`head`有可能会改变。这里`head 从1->3`, `dummy (List(0))`保持不变。
### 复杂度分析
* *时间复杂度:* `O(n) - n is number of Linked List`
* *空间复杂度:* `O(1)`
## 关键点分析
1. 创建一个dummy node
2. 对链表以k为单位进行分组，记录每一组的起始和最后节点位置
3. 对每一组进行翻转，更换起始和最后的位置
4. 返回`dummy.next`.
## 代码 (`Java/Python3`)
*Java Code*
```java
class ReverseKGroupsLinkedList {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode start = dummy;
ListNode end = head;
int count = 0;
while (end != null) {
count++;
// group
if (count % k == 0) {
// reverse linked list (start, end]
start = reverse(start, end.next);
end = start.next;
} else {
end = end.next;
}
}
return dummy.next;
}
/**
* reverse linked list from range (start, end), return last node.
* for example:
* 0->1->2->3->4->5->6->7->8
* | |
* start end
*
* After call start = reverse(start, end)
*
* 0->3->2->1->4->5->6->7->8
* | |
* start end
* first
* @return the reversed list's 'start' node, which is the precedence of node end
*/
private ListNode reverse(ListNode start, ListNode end) {
ListNode curr = start.next;
ListNode prev = start;
ListNode first = curr;
while (curr != end){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
start.next = prev;
first.next = curr;
return first;
}
}
```
*Python3 Cose*
```python
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if head is None or k < 2:
return head
dummy = ListNode(0)
dummy.next = head
start = dummy
end = head
count = 0
while end:
count += 1
if count % k == 0:
start = self.reverse(start, end.next)
end = start.next
else:
end = end.next
return dummy.next
def reverse(self, start, end):
prev, curr = start, start.next
first = curr
while curr != end:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
start.next = prev
first.next = curr
return first
```
## 参考（References)
* [Leetcode Discussion (yellowstone)](https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11440/Non-recursive-Java-solution-and-idea)
## 扩展
* 要求从后往前以`k`个为一组进行翻转。**(字节跳动（ByteDance）面试题)**
例子，`1->2->3->4->5->6->7->8, k = 3`,
从后往前以`k=3`为一组，
* `6->7->8` 为一组翻转为`8->7->6`，
* `3->4->5`为一组翻转为`5->4->3`.
* `1->2`只有2个nodes少于`k=3`个，不翻转。
最后返回： `1->2->5->4->3->8->7->6`
这里的思路跟从前往后以`k`个为一组进行翻转类似，可以进行预处理：
1. 翻转链表
2. 对翻转后的链表进行从前往后以k为一组翻转。
3. 翻转步骤2中得到的链表。
例子：`1->2->3->4->5->6->7->8, k = 3`
1. 翻转链表得到：`8->7->6->5->4->3->2->1`
2. 以k为一组翻转： `6->7->8->3->4->5->2->1`
3. 翻转步骤#2链表： `1->2->5->4->3->8->7->6`
## 类似题目
* [Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://snowan.gitbook.io/study-notes/leetcode/zhong-wen-ban-jie-ti/25.reverse-nodes-in-k-groups-cn.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.