Reorder List

Q: 为什么要反转列表的后半部分？

答案会从最后一个节点到第一个节点读取后半部分，而单向链表只能向前遍历。将后半部分反转一次，耗时为 O(n) ，这样合并时就能向前遍历两部分。

Q: 重新排列列表的时间复杂度是多少？

原地方法的时间复杂度为 O(n) ，额外空间复杂度为 O(1) ：查找中间节点、反转和交织这些操作都会以常数次遍历每个节点。将值复制到数组中，时间复杂度也是 O(n) ，但需要 O(n) 的空间；而每次将尾部向前移动一个节点，时间复杂度为 O(n²) 。

Q: 当列表中的节点数量为偶数时，中间位置在哪里？

让慢指针停在前半部分的最后一个节点上。对于 6 个节点，前后两半各有 3 个；对于 5 个节点，前半部分有 3 个，后半部分有 2 个。多出的那个节点就是答案的末尾，也就是按顺序排列时中间值所在的位置。

中等链表快慢指针双指针

+10

你会得到一个单向链表，它存储在两个长度相同的数组中。节点 i 保存值 values[i]，并链接到节点 next[i]。-1 表示链表结束，头节点是节点 0。节点在数组中的存储顺序并非链表顺序，因此要沿着链接遍历。

按链表顺序将节点称为 L0, L1, ..., Lk。重新排列链表，使其顺序变为 L0, Lk, L1, Lk-1, L2, Lk-2, ...：先放第一个节点，再放最后一个节点，然后放第二个节点，再放倒数第二个节点，以此类推。按新顺序返回这些值。

函数

reorderList(next: integer-array, values: integer-array) → integer-array

nextinteger-array: 每个节点所链接的节点的索引，最后一个节点为 -1
valuesinteger-array: 每个节点所保存的值
返回值integer-array: 按重新排序后的列表顺序排列的值

约束条件

1 ≤ n ≤ 4000，其中 n 是 next 和 values 的长度。
-1000 ≤ values[i] ≤ 1000
每个 next[i] 都是 -1，或从 0 到 n-1 的节点索引。
从节点 0 开始，列表会恰好访问每个节点一次，然后到达 -1。不存在循环。

示例

输入: next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
输出: [1, 5, 2, 4, 3]
解释: 沿着从节点 0 出发的链接，列表依次为 1, 2, 3, 4, 5。第一个、最后一个、第二个和倒数第二个分别是 1, 5, 2, 4，中间值 3 最后出现。

输入: next = [2, 3, 1, -1]values = [10, 30, 20, 40]
输出: [10, 40, 20, 30]
解释: 列表依次访问节点 0, 2, 1, 3，并读取 10, 20, 30, 40。第一个和最后一个给出 10, 40，然后中间的一对给出 20, 30。

输入: next = [-1]values = [7]
输出: [7]
解释: 只有一个节点的列表没有需要移动的内容，所以答案是 [7]。

进阶

你能用 O(1) 的额外内存重新排列链接本身吗？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

新的顺序在前半部分和后半部分之间交替，但单向链表只能向前遍历。把这个任务分成三个常见的链表操作：用慢指针和快指针找到中间位置，反转后半部分，然后将两部分交织在一起，每次处理一个节点。

每次将尾指针向前移动一个节点

思路

这里的指针是节点索引，向前移动的方式是 node = next[node]。第一个节点后面是最后一个节点，因此先摘下最后一个节点，并将它插入当前节点之后，然后再向后移动两个节点，重复操作。对于 1, 2, 3, 4, 5，结果是 1, 5, 2, 3, 4，然后是 1, 5, 2, 4, 3。当当前节点后面不足两个节点时停止。

要找到倒数第二个节点，每一轮都要一路遍历到末尾。每轮遍历的节点数减少两个，总共大约需要 n²/4 次移动：4000 个节点需要四百万次移动。

算法

将 cur = 0 设为初始值。
当 cur 后面至少还有两个节点时，从 cur 开始沿链表遍历 before，直到 next[next[before]] == -1，此时 tail = next[before] 是最后一个节点。
将它移出链表：next[before] = -1，然后插入：next[tail] = next[cur] 和 next[cur] = tail。
将 cur 移到 next[tail]，然后重复操作。
从节点 0 开始遍历并收集值。

def reorderList(next, values):
    cur = 0
    # While at least two nodes follow cur, move the last node right after cur.
    while next[cur] != -1 and next[next[cur]] != -1:
        before = cur
        while next[next[before]] != -1:  # find the node before the tail
            before = next[before]
        tail = next[before]
        next[before] = -1
        next[tail] = next[cur]
        next[cur] = tail
        cur = next[tail]
    result = []
    node = 0
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

复制这些值，并从两端读取

思路

数组只需一步就能到达最后一个元素。按列表顺序复制这些值，第一个示例中是 [1, 2, 3, 4, 5]，然后用 lo 从前面读取，用 hi 从后面读取：取 lo，取 hi，并在 lo < hi 时让两者同时向中间移动。这样会得到 1, 5, 2, 4；长度为奇数时，两者会在中间的 3 相遇，它会排在最后。

这需要 O(n) 时间和 O(n) 额外内存，而且链接不会改变。

算法

从节点 0 开始遍历，并将每个值追加到 inOrder。
将 lo 设为 0，将 hi 设为最后一个索引。
当 lo < hi 时，追加 inOrder[lo] 和 inOrder[hi]，然后将 lo 加 1，将 hi 减 1。
如果 lo == hi，则追加中间的值。

def reorderList(next, values):
    # Write the values out in list order.
    in_order = []
    node = 0
    while node != -1:
        in_order.append(values[node])
        node = next[node]
    # Take from the front and the back in turn.
    result = []
    lo, hi = 0, len(in_order) - 1
    while lo < hi:
        result.append(in_order[lo])
        result.append(in_order[hi])
        lo += 1
        hi -= 1
    if lo == hi:  # odd length: the middle value comes last
        result.append(in_order[lo])
    return result

找到中间部分，将后半部分反转，再交错合并

思路

对于 1, 2, 3, 4, 5, 6，答案是 1, 6, 2, 5, 3, 4：前半部分 1, 2, 3 按顺序排列，与反向读取的后半部分 4, 5, 6 交替出现。因此，在中间位置切开列表，将后半部分反转，然后交错编织。

slow 每次移动一个链接，而 fast 每次移动两个链接，因此 slow 会停在前半部分的最后一个节点上，也就是 3，无论有五个还是六个节点都是如此。在它后面切开，长度为奇数时，前半部分会多出一个节点，而这个节点会成为答案的末尾。交错编织时，两部分各取一个节点，直到后半部分取完。

每个节点都会被访问常数次，只需少量索引作为内存开销。R 会在链接向量首次发生变化时复制它，因此在 R 中，内存复杂度为 O(n)。

算法

当 next[fast] 和 next[next[fast]] 都不等于 -1 时，让 slow 前进一个节点，让 fast 前进两个节点。
设置 second = next[slow]，然后设置 next[slow] = -1。
反转从 second 开始的列表，新头节点是 prev。
交错合并：当 second 不等于 -1 时，将 first 连接到 second，再将 second 连接到原来的 next[first]，然后让两者都前进。
从节点 0 开始遍历并收集值。

def reorderList(next, values):
    # 1. Find the middle: slow stops on the last node of the first half.
    slow = fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    second = next[slow]
    next[slow] = -1  # cut the list in two
    # 2. Reverse the second half.
    prev = -1
    while second != -1:
        after = next[second]
        next[second] = prev
        prev = second
        second = after
    # 3. Weave: one node from the front half, one from the reversed back half.
    first, second = 0, prev
    while second != -1:
        first_after, second_after = next[first], next[second]
        next[first] = second
        next[second] = first_after
        first, second = first_after, second_after
    result = []
    node = 0
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

易错点和边界情况

没有在列表中间断开。如果没有 next[slow] = -1，前半部分仍会指向后半部分，交错合并后，列表就会循环回自身。
保存链接前就覆盖它。在反转和交错合并过程中，先将 next[node] 读入变量，否则列表的其余部分就会丢失。
一直交错合并到前半部分结束。长度为奇数时，循环会多运行一次，此时 second 的值为 -1，并读取 next[-1]。
把数组顺序当作列表顺序。在第一个示例中，values 是 [1, 3, 5, 2, 4]，但列表的顺序是 1, 2, 3, 4, 5。
在 Lua 和 R 中，数组从 1 开始。节点索引保持从 0 开始，并读取 next[node + 1]。

常见问题3

为什么要反转列表的后半部分？

答案会从最后一个节点到第一个节点读取后半部分，而单向链表只能向前遍历。将后半部分反转一次，耗时为 O(n)，这样合并时就能向前遍历两部分。

重新排列列表的时间复杂度是多少？

原地方法的时间复杂度为 O(n)，额外空间复杂度为 O(1)：查找中间节点、反转和交织这些操作都会以常数次遍历每个节点。将值复制到数组中，时间复杂度也是 O(n)，但需要 O(n) 的空间；而每次将尾部向前移动一个节点，时间复杂度为 O(n²)。

当列表中的节点数量为偶数时，中间位置在哪里？

让慢指针停在前半部分的最后一个节点上。对于 6 个节点，前后两半各有 3 个；对于 5 个节点，前半部分有 3 个，后半部分有 2 个。多出的那个节点就是答案的末尾，也就是按顺序排列时中间值所在的位置。

def reorderList(next, values):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

next = [3, 4, -1, 1, 2]
values = [1, 3, 5, 2, 4]

预期输出

[1, 5, 2, 4, 3]