# 25.reverse-nodes-in-k-groups-cn

## 题目地址

https://leetcode.com/problems/reverse-nodes-in-k-group/

## 题目描述

``````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:

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.``````

## 思路

``````ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;``````

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`.

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

``````class ReverseKGroupsLinkedList {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
}
ListNode dummy = new ListNode(0);

ListNode start = dummy;
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

``````class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if head is None or k < 2:
dummy = ListNode(0)
start = dummy
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``````

## 扩展

• 要求从后往前以`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`

1. 翻转链表

2. 对翻转后的链表进行从前往后以k为一组翻转。

3. 翻转步骤2中得到的链表。

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`

Last updated