Middle of the Linked List
给你一个单向链表，存储在两个长度相同的数组中。节点 i 的值为 values[i]，并链接到节点 next[i]。-1 表示链表结束，头节点是节点 0。节点在数组中的存储顺序与链表顺序不同，所以要沿着链接遍历。
返回中间节点的值。如果链表的节点数是偶数，就有两个中间节点，返回第二个中间节点的值。
函数
- valuesinteger-array
- 每个节点保存的值
- nextinteger-array
- 每个节点所链接的节点的索引，最后一个节点为 -1
- 返回值integer
- 中间节点的值，如果长度为偶数，则取第二个中间节点的值
约束条件
1 ≤ n ≤ 5000，其中n是values和next的长度。-104 ≤ values[i] ≤ 104- 每个
next[i]都是-1，或是从0到n-1的节点索引。 - 从节点
0开始，列表会恰好访问每个节点一次，然后到达-1。这里没有循环。
示例
- 输入
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- 输出
- 5
- 解释
- 从节点
0开始沿着链接访问，会依次经过节点0, 3, 4, 2, 1，它们的值依次为4, 7, 5, 2, 9。中间位置对应的是节点4，值为5，而不是数组中间位置的元素values[2] = 2。
- 输入
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- 输出
- 40
- 解释
- 这里的节点按顺序存储。六个节点有两个中间节点，
30和40，第二个胜出。
- 输入
- values = [8]next = [-1]
- 输出
- 8
- 解释
- 只有一个节点的列表，其中间位置就是它本身。
进阶
你能否只遍历一次，就返回列表中位于三分之一处的节点？每个指针移动的速度应该是多少，你会在哪里停下？
提示
逐个打开提示，每个都会多透露一点。
直到到达列表末尾，你才知道列表的长度。如果两个行走者从列表头部出发，其中一个的速度是另一个的两倍，会怎么样？
当较快的指针到达末尾时，较慢的指针走过了全程的一半，因此它停在中间节点上。剩下唯一需要考虑的是何时停止，才能在长度为偶数时停在第二个中间节点上。
让
slow和fast从节点0开始。当fast不等于-1且next[fast]不等于-1时，让 slow 前进一个链接，让 fast 前进两个链接。然后返回values[slow]。
题解
链表没有索引：你只能一路遍历到末尾，经过中间位置后，才能知道它的长度。你可以把它复制到数组中，也可以先计数，再遍历一次。用两个速度不同的指针只需遍历一次：快指针走到尽头时，慢指针正好走到一半。
将这些值复制到数组中
思路
遍历列表一次，并将每个值追加到数组中：第一个示例中的 [4, 7, 5, 2, 9]。数组按列表顺序保存这些值，因此中间位置的索引是 length / 2，并采用整数除法。当长度为偶数时，这会得到第二个中间位置：6 个值对应索引 3，也就是第二个示例中的 40。遍历需要 O(n) 时间，复制需要额外的 O(n) 内存。
算法
- 从一个空数组开始，并设置
node = 0。 - 当
node不等于-1时，追加values[node]，并移动到next[node]。 - 返回索引为
length / 2（向下取整）的条目。
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]先数一数，然后走到一半
思路
你只需要长度，不需要复制。数出节点数量，回到头节点，然后走 length / 2 步，向下取整。走了 k 步后，你就位于位置 k，把头节点算作 0；length / 2 就是中间位置：长度为 5 时的位置 2，以及长度为 6 时的第二个中间位置 3。在第一个示例中，你数出 5，然后按 0 → 3 → 4 走，读取 values[4] = 5。
内存占用降至 O(1)。代价是要再次遍历列表的一半，总共移动 1.5n 步。
算法
- 从节点
0开始，走到-1，并统计节点数。 - 返回节点
0。 - 将
node = next[node]执行count / 2次，向下取整。 - 返回
values[node]。
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]快慢指针
思路
每轮中，slow 前进一个节点，fast 前进两个节点，所以经过 k 轮后，slow 位于位置 k，而 fast 位于位置 2k。当 fast 到达末尾时，slow 正好位于中间，而且你不需要知道长度。
停止条件决定你会得到哪个中间节点。循环条件是 fast != -1 且 next[fast] != -1。长度为奇数时，fast 会停在最后一个节点。长度为偶数时，它会越过末尾到达 -1，这会让 slow 再前进一个节点，来到第二个中间节点。在第二个示例中，slow 依次经过 0, 1, 2, 3，而 fast 依次经过 0, 2, 4, -1，所以答案是 values[3] = 40。整个过程只需遍历一遍，并使用两个整数的内存。
算法
- 将
slow = 0和fast = 0。 - 当
fast != -1且next[fast] != -1时，将slow = next[slow]和fast = next[next[fast]]。 - 返回
values[slow]。
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
易错点和边界情况
- 返回
values[n / 2]。节点并不是按列表顺序存储的，所以在第一个示例中，这会返回2，而不是5。 - 在偶数长度的情况下，找到第一个中间节点。如果循环在
next[fast]和next[next[fast]]都有效时继续运行，就会提前一轮停止，在第二个示例中返回30，而不是40。 - 在检查
fast != -1之前检查next[fast]。在偶数长度的情况下，fast会变成-1，读取next[-1]会导致大多数语言崩溃。在 Python 中，它会静默地读取最后一项。 - 在计数方法中，走
count / 2 - 1步，或向上取整。将头节点计为位置0。
常见问题3
查找链表中间位置的时间复杂度和空间复杂度是多少？
这三种方法的时间复杂度都是 O(n)，因为你至少要遍历列表的一半。复制这些值会额外使用 O(n) 的内存。先计数的方法和快慢指针都只使用 O(1) 的额外空间，而快慢指针只需遍历一次。
怎样返回第一个中间节点，而不是第二个？
更改停止规则，让快指针提前一轮停止：当 next[fast] != -1 且 next[next[fast]] != -1 时循环。对于 6 个节点，慢指针会停在位置 2，而不是 3。在计数方法中，移动 (count - 1) / 2 步，而不是 count / 2。
快慢指针技巧还会用于哪些地方？
同样的两种速度也能检测链表中的循环：在循环中，快指针会追上慢指针，两者相遇。它们还能找到循环的起点，也能将列表分成两半，用于归并排序，或检查列表正序和倒序读取时是否相同。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def middleNode(values, next):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
预期输出
5