Reverse Nodes in k-Group
单向链表存储在两个长度相同的数组中。节点 i 保存 values[i]，并链接到节点 next[i]；-1 表示链表结束，头节点是节点 0。节点可以按任意顺序存储，因此要沿着链接遍历，而不是按数组顺序遍历。
按每组 k 个节点反转链表：前 k 个节点反转，然后是接下来的 k 个节点，以此类推。最后一组如果少于 k 个节点，则保持原有顺序。按新链表的顺序返回这些值。
函数
- nextinteger-array
- 每个节点所链接的节点的索引；如果是最后一个节点，则为 -1
- valuesinteger-array
- 每个节点保存的值
- kinteger
- 每组中要反转的节点数
- 返回值integer-array
- 新列表中的值顺序
约束条件
1 ≤ L ≤ 5000，其中L是next和values的长度。-1000 ≤ values[i] ≤ 10001 ≤ k ≤ L- 每个
next[i]都是-1，或者是从0到L-1的节点索引。 - 从节点
0开始，列表会恰好访问每个节点一次，然后到达-1。不存在循环。
示例
- 输入
- next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
- 输出
- [2, 1, 4, 3, 5]
- 解释
- 列表读取为
1, 2, 3, 4, 5（节点0, 2, 4, 1, 3）。数对1, 2和3, 4的顺序颠倒了，而5单独的长度小于k = 2，所以它留在最后。
- 输入
- next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
- 输出
- [30, 20, 10, 60, 50, 40, 70, 80]
- 解释
- 列表读出
10, 20, ..., 80。组10, 20, 30和40, 50, 60的顺序被反转了。70, 80比k = 3短，因此保持原来的顺序。
- 输入
- next = [2, -1, 1]values = [7, 9, 3]k = 3
- 输出
- [9, 3, 7]
- 解释
- 数组的顺序是
7, 9, 3，但列表的顺序是7, 3, 9。当k等于长度时，整个列表就是一组，结果会反转为9, 3, 7。
进阶
你能用递归的方式编写它吗？每次反转一组，再对列表的其余部分递归处理。这会使用多少额外内存？
提示
逐个打开提示，每个都会多透露一点。
反转整个列表时，需要用两个指针遍历列表，一个指向前一个节点，另一个指向当前节点，并在经过每个节点时翻转链接。如果遍历必须在经过
k个节点后停止，而且列表的其余部分必须保持连接，会有什么变化？翻转一组节点之前，先向前走
k步，检查是否存在k个节点；如果不存在，就保持其余部分不变。你到达的节点紧跟在这一组之后，这一组的第一个节点最终必须指向它。- 保留已经处理完的部分的最后一个节点。翻转一组节点后，让这个节点指向该组新的第一个节点（对于第一组，该节点就是新的头节点）。该组原来的第一个节点现在是已处理部分的最后一个节点。
题解
反转整个列表只需遍历一遍并翻转链接。这里每隔 k 个节点就停止翻转，并且每个反转后的分组都必须与前面的部分和后面的节点连接起来。你可以把值复制到数组中，再反转各个区块；也可以在原地重新连接每个分组，额外内存为 O(1)。
复制这些值，并将每个区块反转
思路
从节点 0 开始遍历，使用 node = next[node]，并按列表顺序将值复制到数组中。现在，各组对应的索引块分别是 0 到 k-1、k 到 2k-1，以此类推：反转每个完整的块，较短的最后一块保持不变。这个过程需要 O(L) 时间和 O(L) 额外内存，并且不会触碰任何链接。
算法
- 从节点
0遍历到-1，并将values[node]追加到数组中。 - 对于
start = 0, k, 2k, ...，当start + k ≤ L时：反转从索引start到start+k-1的数据块。 - 末尾较短的数据块保持不变。
- 返回数组。
def reverseKGroup(next, values, k):
# Read the values in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Reverse every full block of k; a shorter last block stays as it is.
for start in range(0, len(order) - k + 1, k):
order[start:start + k] = order[start:start + k][::-1]
return order通过重新链接来反转每个组
思路
要反转整个列表，你需要用 prev 和 node 遍历列表，并设置 next[node] = prev。反转一组节点的做法相同，只需重复循环 k 次，并让 prev 从 after 开始，也就是组后面的那个节点。组中的第一个节点会变成最后一个节点，并指向 after，这样列表的其余部分仍然连接在一起。
反转之前，先数出 k 个节点：如果先遇到 -1，说明剩下的节点组成一个较短的组，保持不变。反转后，prev 就是该组新的第一个节点。将上一组的最后一个节点连接到它，或者在这是第一组时将它设为头节点。该组原来的第一个节点现在是已完成部分的最后一个节点。
每个节点会被访问两次，一次用于计数，一次用于反转：时间复杂度为 O(L)，只需占用少量整数的内存（在 R 中为 O(L)，因为首次修改链接向量时会复制它）。
算法
- 从
head = 0、prevTail = -1、groupStart = 0开始。 - 从
groupStart开始向后走k步，到达after；如果先到达-1，则转到第 5 步。 - 令
prev = after和node = groupStart，重复k次：保存next[node]，设置next[node] = prev，然后将两者都向后移动。 - 如果
prevTail是-1，则设置head = prev；否则设置next[prevTail] = prev。设置prevTail = groupStart、groupStart = after；转到第 2 步。 - 从
head开始收集这些值。
def reverseKGroup(next, values, k):
head = 0 # the list's head; changes after the first group
prev_tail = -1 # last node of the groups already reversed
group_start = 0
while True:
# Find the node right after this group, or stop if fewer than k remain.
after, count = group_start, 0
while after != -1 and count < k:
after = next[after]
count += 1
if count < k:
break
# Turn the group's k links around. Its first node ends up last
# and links to the node after the group.
prev, node = after, group_start
for _ in range(k):
following = next[node]
next[node] = prev
prev, node = node, following
# prev is the group's new first node: hang it after the previous group.
if prev_tail == -1:
head = prev
else:
next[prev_tail] = prev
prev_tail = group_start
group_start = after
# Walk the relinked list from its head.
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
易错点和边界情况
- 翻转末尾较短的分组。翻转前先数出
k个节点；翻转后的链接无法在不再遍历一次的情况下恢复。 - 像完整反转那样，从
prev = -1开始翻转。这样较短的尾部会脱落：第一个示例返回2, 1, 4, 3。 - 没有将前一组的最后一个节点链接到新的第一个节点。它仍然指向旧的第一个节点，因此会有
k-1个节点消失。 - 从节点
0读取答案，或从左到右读取values。一组k ≥ 2个节点翻转后，节点0就不是头节点，而且数组顺序从来就不是列表顺序。 - 在 Lua 和 R 中使用从 0 开始的索引，但它们的数组从 1 开始。节点索引保持从 0 开始，并读取
next[node + 1]。
常见问题3
按 k 组反转节点的时间复杂度和空间复杂度是多少？
对于包含 L 个节点的列表，它的运行时间为 O(L)：每个节点都会被计数一次并翻转一次。原地版本使用 O(1) 的额外内存；将值复制到数组中则使用 O(L) 的内存。
如果最后一组的节点少于 k 个，会发生什么？
它会保留原来的顺序。每次翻转一组之前，先数出 k 个节点；如果先到达列表末尾，就保持其余部分不变。
为什么这个问题的答案会使用一个虚拟节点？
使用节点对象时，在头节点前放置一个虚拟节点，可以让第一组前面也有一个节点，这样一行代码就能把每一组都连接到已完成的部分。使用链接数组时，直到第一组处理完毕，prevTail 都保持为 -1，作用相同。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def reverseKGroup(next, values, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
next = [2, 3, 4, -1, 1] values = [1, 4, 2, 5, 3] k = 2
预期输出
[2, 1, 4, 3, 5]