## [Leetcode]25. Reverse Nodes in k-Group(C++)

### 题目描述

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 个节点进行重复操作

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode();
ListNode* last_tail = dummy;

int len = 0;
while (curr) {
len++;
if (len == k) {
// store the node just after next k nodes

curr->next = nullptr;

// reverse next k nodes

// the last node of next k nodes should be the head of
last_tail->next = curr;

// the head of next k nodes now should be the last of
// next k nodes

// reset
len = 0;
} else {
curr = curr->next;
}
}

return dummy->next;
}

private:

ListNode* prev = nullptr;

while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
}
};
``````
• 时间复杂度: O(n)
• 空间复杂度: O(1)

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

Built with Hugo
Theme Stack designed by Jimmy