Reverse Linked List
给你一个存储在数组 next 中的单向链表：节点 i 指向节点 next[i]，-1 表示链表结束，头节点是节点 0。节点在数组中的存储顺序并不是链表顺序，因此要沿着链接遍历。
反转链表，即调转每个链接的方向，使原来的最后一个节点成为头节点，节点 0 成为最后一个节点，并指向 -1。返回更新后的 next 数组，其长度与输入数组相同。
函数
- nextinteger-array
- 每个节点所链接节点的索引，最后一个节点为 -1
- 返回值integer-array
- 反转后列表中的下一个数组
约束条件
1 ≤ next.length ≤ 5000- 每个
next[i]都是-1，或者是从0到next.length-1的节点索引。 - 从节点
0开始，列表会恰好访问每个节点一次，然后到达-1。这里没有环。
示例
- 输入
- next = [1, 2, 3, -1]
- 输出
- [-1, 0, 1, 2]
- 解释
- 反转后，
0 → 1 → 2 → 3变成3 → 2 → 1 → 0：每个节点都指向它前面的节点，而节点0指向-1。
- 输入
- next = [2, -1, 3, 1]
- 输出
- [-1, 3, 0, 2]
- 解释
- 反转后，
0 → 2 → 3 → 1变成1 → 3 → 2 → 0。每个新链接都位于其节点对应的索引处：[-1, 3, 0, 2]，而不是反转后的数组[1, 3, -1, 2]。
- 输入
- next = [-1]
- 输出
- [-1]
- 解释
- 一个节点的反向仍然是它本身。它仍然是头节点和尾节点，并且仍然指向
-1。
进阶
你能只反转列表中位置 left 和位置 right 之间的部分，并让前后的节点保持原位吗？
提示
逐个打开提示，每个都会多透露一点。
每条链接
a → b都必须变成b → a。站在一个节点上，你需要知道什么才能反转它的链接？你需要找到你从哪里来的节点，所以遍历列表时要记住前一个节点。但一旦覆盖
next[node]，前进的路径就消失了。在更改任何内容之前，先把它保存下来。从
prev = -1和node = 0开始。当node不等于-1时：记住next[node]，将next[node]设为prev，然后将prev移到node，并将node移到保存的值。返回next。
题解
反转列表不会移动任何节点，而是把每个链接反过来。节点的链接是你访问列表其余部分的唯一途径，因此一旦覆盖它，后面的所有内容都会丢失。你可以先记下顺序，也可以先遍历一遍，在反转每个链接之前保存前进方向。
记下顺序，然后重新链接
思路
这里的指针是节点索引，向前移动的方式是 node = next[node]。从节点 0 开始，沿着链走到 -1，并记下节点：第二个示例中的顺序是 [0, 2, 3, 1]。在反转后的列表中，每个节点都链接到该顺序中它前面的节点，而原来的头节点链接到 -1。把这些链接写入一个新数组，这样在仍需要原数组时就不会覆盖其中的内容。
这种方法需要 O(n) 的时间，以及 O(n) 的额外内存来存储顺序和新数组。
算法
- 从节点
0遍历到-1，并将每个节点追加到order。 - 创建一个长度相同的新数组。
- 将
order[0]对应的项设为-1。 - 对于每个
k ≥ 1，将order[k]对应的项设为order[k-1]。 - 返回新数组。
def reverseList(next):
order = []
node = 0
while node != -1:
order.append(node)
node = next[node]
reversed_next = [0] * len(next)
reversed_next[order[0]] = -1 # the old head ends the new list
for k in range(1, len(order)):
reversed_next[order[k]] = order[k - 1]
return reversed_next一遍就能反转链接
思路
每到达一个节点，就立即反转它的链接，并在 prev 中记住你从哪个节点来。它的初始值是 -1，因为旧的头节点会变成最后一个节点。设置 next[node] = prev 会抹去你唯一的前进路径，所以要先把它保存到 after 中。
任何时刻，你身后的节点都会组成一个反转后的列表，头节点是 prev；前方的节点则保持不变，从 node 开始。当 node 到达 -1 时，所有链接都已反转，prev 就是新的头节点。在第二个示例中，遍历过程会写入 next[0] = -1、next[2] = 0、next[3] = 2 和 next[1] = 3。
每个节点只访问一次，时间复杂度为 O(n)，使用 3 个整数的内存。
算法
- 将
prev = -1和node = 0设好。 - 当
node不等于-1时，保存after = next[node]。 - 设置
next[node] = prev。 - 继续：
prev = node，然后node = after。 - 返回
next。
def reverseList(next):
prev = -1 # the node behind the current one; the old head will point to -1
node = 0
while node != -1:
after = next[node] # save the rest of the list before cutting the link
next[node] = prev
prev = node
node = after
return next
易错点和边界情况
- 在保存
next[node]之前就覆盖它。这样会丢失原来的前向链接，遍历会向后跳，而不是继续到下一个节点。 - 将
prev初始化为0，而不是-1。这样节点0就会链接到自身。 - 反转数组，而不是反转链接。
[2, -1, 3, 1]会变成[1, 3, -1, 2]，而不是[-1, 3, 0, 2]。 - 当
next[node] != -1时循环。这样最后一个节点的链接永远不会被反转；应当在node != -1时循环。 - 在 Lua 和 R 中，数组从 1 开始。节点索引仍使用从 0 开始的编号，并读取
next[node + 1]。
常见问题3
反转链表的时间复杂度和空间复杂度是多少？
迭代版本会访问每个节点一次，时间复杂度为 O(n)，并保留 3 个指针，额外空间复杂度为 O(1)。先将顺序复制到数组中，时间复杂度也是 O(n)，但需要 O(n) 的额外空间。递归版本需要 O(n) 的调用栈空间。
你能用递归反转链表吗？
是的。反转头节点之后的所有内容，然后让头节点原来的下一个节点指回头节点，并将头节点的链接设为空。这样读起来很清楚，但每个节点都会产生一次嵌套调用，因此较长的列表可能会导致调用栈溢出。Python 默认在 1000 次调用后停止，而包含 5000 个节点的列表会超过这个限制。
为什么反转链表需要三个指针？
要反转一个节点的链接，你需要这个节点本身和它前面的节点，也就是两个指针。第三个指针保存它后面的节点，因为反转链接会抹掉指向列表其余部分的唯一引用。没有它，遍历就无法继续。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def reverseList(next):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
next = [1, 2, 3, -1]
预期输出
[-1, 0, 1, 2]