0%

### 题目描述

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.

### 例子

#### 例子 1

Input: `head = [1,2,3,4,5], k = 2`
Output: `[2,1,4,3,5]`

#### 例子 2

Input: `head = [1,2,3,4,5], k = 3`
Output: `[3,2,1,4,5]`

#### 例子 3

Input: `head = [1,2,3,4,5], k = 1`
Output: `[1,2,3,4,5]`

• Could you solve the problem in `O(1)` extra memory space?
• You may not alter the values in the list’s nodes, only nodes itself may be changed.

### Constraints

• The number of nodes in the list is in the range `sz`.
• `1 <= sz <= 5000`
• `0 <= Node.val <= 1000`
• `1 <= k <= sz`

### 解题思路

• 保存前 k 个节点的尾 `prev_tail`，和当前 k 个节点的头 `curr_head`
• 在第 k 个节点 `curr_tail` 时先保持好下一个节点作为下 k 个节点的头 `next_head` ，然后断开（`curr_tail->next = nullptr`
• 翻转当前 k 个节点 `reverse(curr_head)`
• 让前 k 个节点的尾指向保存原先的第 k 个节点（现在是翻转后的 k 个节点的头）`prev_tail->next = curr_tail`
• 重置这个节点，对下 k 个节点进行重复操作

• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 25.ReverseNodesInKGroup.cpp

GitHub: Leetcode-C++-Solution