Remove Nth Node From End of List
你会得到一个单向链表，它存储在两个长度相同的数组中。节点 i 保存值 values[i]，并链接到节点 next[i]。-1 表示链表结束，头节点是节点 0。节点的存储顺序与链表顺序不同，因此要沿着链接遍历。
删除从链表末尾开始数的第 n 个节点，其中最后一个节点是从末尾开始数的第 1 个节点。按链表顺序返回剩余节点的值。
函数
- valuesinteger-array
- 每个节点所持有的值
- nextinteger-array
- 每个节点指向的节点索引，最后一个节点则为 -1
- ninteger
- 从末尾开始计数，要删除哪个节点，其中 1 表示最后一个节点
- 返回值integer-array
- 列表中剩余的值，按顺序排列；移除唯一节点后为空
约束条件
1 ≤ L ≤ 5000，其中L是values和next的长度。-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- 每个
next[i]都是-1，或是从0到L-1的节点索引。 - 从节点
0开始，列表恰好访问每个节点一次，然后到达-1。不存在循环。
示例
- 输入
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- 输出
- [5, 2, 6, 7]
- 解释
- 从节点
0沿着链接往下看，列表是5, 2, 6, 9, 7。倒数第 2 个是9，位于节点1；移除它后，剩下5, 2, 6, 7。
- 输入
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- 输出
- [20, 30, 40]
- 解释
- 有 4 个节点，且
n = 4：从末尾数第 4 个节点就是头节点。现在，列表从节点1开始，内容依次为20, 30, 40。
- 输入
- values = [42]next = [-1]n = 1
- 输出
- []
- 解释
- 唯一的节点既是头节点，也是最后一个节点。移除它后，列表就会变空，所以答案是
[]。
进阶
你能否在一次遍历中找到并断开该节点，而不先计算长度？
提示
逐个打开提示，每个都会多透露一点。
列表只能向前遍历，而这个节点是按它与末尾的距离来定义的。如果你知道长度
L，它从开头数起位于哪个位置？你必须更改哪个节点的链接才能将它移除？你可以在不知道长度的情况下测量到末尾的距离。让一个指针比另一个指针提前
n个节点，然后同时移动它们。当领先的指针到达最后一个节点时，跟随的指针正好位于要删除的节点之前。让
fast向前移动n次。如果此时它是-1，那么头节点就是要删除的节点，因此列表从next[0]开始。否则，当next[fast] != -1时，让slow和fast一起移动，然后设置next[slow] = next[next[slow]]。从头节点开始遍历列表，并收集各个值。
题解
目标节点是从末尾开始计数的，但单向链表只能向前遍历，而且要移除一个节点，必须停在它前面的节点上。让两个指针之间相隔 n 个节点：当前面的指针到达最后一个节点时，后面的指针正好停在目标节点前面。下面，L 表示节点数。
将这些值复制到数组中
思路
这里的指针是节点索引，向前移动就是 node = next[node]。遍历一次，并将每个值追加到数组中：第一个示例中的 [5, 2, 6, 9, 7]。倒数第 n 个元素位于索引 L-n 处，这里是 5-2 = 3，也就是 9。删除它并返回其余元素。
它的时间复杂度为 O(L)，额外空间复杂度为 O(L)，而且不会修改任何链接。
算法
- 从一个空数组和
node = 0开始。 - 当
node不等于-1时，追加values[node]，并移动到next[node]。 - 删除索引为
length - n的条目。 - 返回数组。
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return order数一数节点，然后取消链接
思路
要删除一个节点，只需让它前一个节点的链接越过它：next[prev] = next[next[prev]]。先遍历一次，统计节点数量。头节点的位置是 0，目标节点的位置是 L-n，因此 prev 距离头节点 L-n-1 步。在第一个示例中，走两步 0 → 2 → 4 就能到达节点 4，而 next[4] = next[1] = 3 会将 9 删除。
当 n = L 时，目标节点就是头节点，它前面没有节点，因此像第二个示例那样，将列表的起点改为 next[0]。两次遍历需要约 2L 步，并占用少量整数内存。
算法
- 从节点
0开始遍历到-1，并将节点数记为L。 - 如果
n == L，新的头节点就是next[0]。 - 否则，将
prev设为节点0，并移动L-n-1次，然后设置next[prev] = next[next[prev]]。 - 从头节点开始遍历，并按顺序收集
values[node]。
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result两个指针相距 n 个节点
思路
让 fast 先前进 n 个链接，让 slow 停在头节点，然后让两者每次各前进一个链接。它们之间始终相隔 n 个节点，因此当 fast 位于最后一个节点（位置 L-1）时，slow 就位于 L-1-n，也就是目标节点前面。你不需要知道 L。
在第一个示例中，fast 依次经过 0 → 2 → 4。然后，slow 移动到 2 和 4，同时 fast 移动到 1 和 3，也就是最后一个节点。此时 next[4] = next[1] = 3 会移除 9。
由于 n ≤ L，只有当 n = L 时，fast 才会在提前前进时到达 -1，这恰好表示头节点就是目标节点。对于节点对象，这个检查起到了哑节点的作用。
算法
- 将
fast = 0，并用fast = next[fast]移动它n次。 - 如果
fast == -1，则目标是头节点：新的头节点是next[0]。 - 否则，将
slow = 0，并在next[fast] != -1时同时移动两者。 - 设置
next[slow] = next[next[slow]]。 - 从头节点开始遍历，并按顺序收集
values[node]。
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
易错点和边界情况
- 删除数组索引
L-n处的条目。节点并不是按列表顺序存储的：在第一个示例中，values[3] = 7是最后一个节点，而不是9。 - 让两个指针一直移动，直到
fast == -1，而不是next[fast] == -1。这样slow会停在目标节点本身，而节点无法解除自身的链接。 - 忘记处理头节点的情况。当
n = L时，fast从头节点出发后会变成-1，此时读取next[fast]会导致程序崩溃。Python 会静默读取next[-1]，并返回错误的列表。 - 移除头节点后，仍从节点
0开始收集答案。应从新的头节点开始最后一次遍历。 - 在 Lua 和 R 中，数组从 1 开始。节点索引保持从 0 开始，并读取
next[node + 1]。
常见问题3
为什么这个问题的答案会使用虚拟节点？
删除一个节点时，需要更改它前一个节点的链接，而头节点没有前一个节点。在头节点前放一个哑节点，就能让每个节点都有前驱节点，因此一行解除链接的代码就能处理所有情况，答案从哑节点的下一个节点开始。不使用哑节点时，检查前导指针是否已经越过列表末尾，也能达到同样的效果。
从末尾删除第 n 个节点的时间复杂度和空间复杂度是多少？
对于包含 L 个节点的列表，需要 O(L) 时间，因为你必须到达末尾才能知道目标在哪里。先计数和双指针方法都只使用 O(1) 的额外内存。将值复制到数组中需要 O(L)。
双指针答案比先计算长度更快吗？
差别不大。两者都是 O(L)，两个指针移动的次数和遍历两次差不多。它的优势在于，你不需要预先知道长度，因此这种方法也适用于只能读取一次的列表。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def removeNthFromEnd(values, next, n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
预期输出
[5, 2, 6, 7]