Sort List
你会得到一个单向链表，它存储在两个长度相同的数组中。节点 i 的值为 values[i]，并链接到节点 next[i]。-1 表示链表结束，头节点是节点 0。节点在数组中的存储顺序与链表顺序不同，而且数组中可能还包含从节点 0 出发遍历时永远无法到达的剩余节点。即使这些节点的链接指向链表中的节点，它们也不属于链表。
按值的非递减顺序对链表排序，并按该顺序返回节点的值。
函数
- 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，且不会重复访问任何节点。 - 从节点
0开始遍历时无法到达的节点不属于该列表。它们的next项可能指向任意位置。
示例
- 输入
- next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
- 输出
- [1, 2, 3, 4, 5]
- 解释
- 从节点
0开始遍历，会访问节点0, 3, 2, 4, 1，因此列表为4, 2, 3, 5, 1。排序后为1, 2, 3, 4, 5。
- 输入
- next = [2, 0, -1, -1]values = [6, 9, -2, 5]
- 输出
- [-2, 6]
- 解释
- 这个列表是
0 → 2，也就是6, -2。从头节点无法到达节点1和3，所以它们的值9和5不会包含在内，尽管节点1链接到节点0。
- 输入
- next = [1, 2, 3, -1]values = [3, -1, 3, -1]
- 输出
- [-1, -1, 3, 3]
- 解释
- 这个列表的内容是
3, -1, 3, -1。相同的值在答案中会按出现次数保留：-1, -1, 3, 3。
进阶
你能在 O(n log n) 时间内通过重新连接节点来排序，而不复制节点中的值吗？
提示
逐个打开提示，每个都会多透露一点。
哪些排序算法需要跳转到任意位置，哪些算法只会沿着输入内容向前遍历？链表很适合后一种。
将两个已排序的列表合并为一个不需要额外的内存：你只需重新连接节点，每次取两个首位值中较小的那个。如果能把列表拆分成两个已排序的部分，一次合并就能完成任务。
用一个慢指针和一个快指针找到中间位置，并在这里将列表断开。用相同的方法对两半进行排序，直到每半只剩一个节点，因为单个节点已经排好序。然后合并这两段有序列表，并返回新的头节点。
题解
快速排序和堆排序依赖随机访问，而单向链表只能向前移动。归并排序很适合：在链表中间拆分链表，以及合并两个有序链表，都只需向前遍历，因此它可以在 O(n log n) 时间内对链表节点进行排序。这里的 n 是数组的长度。
将这些值复制到数组中并排序
思路
列表就是从节点 0 开始，沿着路径遍历 node = next[node]，直到 -1 所访问到的所有值。将这些值收集到一个新数组中，用内置排序功能对其排序，然后返回。你不能直接对 values 排序：在第二个示例中，它包含 9 和 5，但这两个值都不在列表中。
遍历的时间复杂度是 O(n)，排序的时间复杂度是 O(n log n)，额外空间复杂度是 O(n)。列表本身完全不会被修改，这就是面试官会接着问下一种方法的原因。
算法
- 从空数组开始，并将
node = 0。 - 当
node不为-1时，追加values[node]，然后移动到next[node]。 - 按升序对数组排序并返回。
def sortList(next, values):
# Collect the values of the nodes on the list, then sort them.
on_list = []
node = 0
while node != -1:
on_list.append(values[node])
node = next[node]
on_list.sort()
return on_list对链接进行归并排序
思路
慢指针每次移动一个节点，快指针每次移动两个节点，这样遍历一次就能找到中间节点。合并两个有序列表只需要查看它们的头节点：取较小的那个，然后继续向后移动。这两个步骤都不需要第二个数组。
在第一个示例中，slow停在3上，断开它的链接后，4, 2, 3, 5, 1会分成4, 2, 3和5, 1。它们排序后分别是2, 3, 4和1, 5，合并时先取1, 2, 3, 4，再连接剩下的5。
每一层拆分都会对每个节点进行常数次操作，而且大约有log n层，因此时间复杂度是O(n log n)。唯一的额外内存是递归调用栈，对于 4000 个节点来说，大约有 12 层。
算法
- 如果列表只有一个节点（
next[head] == -1），则返回head。 - 设置
slow = head和fast = next[head]；当fast和next[fast]都不为-1时，让slow前进一个链接，让fast前进两个链接。 - 令
second = next[slow]，并用next[slow] = -1断开链表。 - 递归排序两部分。将它们合并：将较小的前端节点链接到
tail后面，直到其中一部分为空，然后链接另一部分的剩余节点。 - 从返回的头节点开始遍历，并收集各个值。
def sortList(next, values):
def merge(a, b):
# Splice two sorted lists into one; on a tie the node from a goes first.
head = tail = -1
while a != -1 and b != -1:
if values[b] < values[a]:
node, b = b, next[b]
else:
node, a = a, next[a]
if tail == -1:
head = node
else:
next[tail] = node
tail = node
next[tail] = a if a != -1 else b # attach whatever is left
return head
def sort(head):
if next[head] == -1: # one node is already sorted
return head
# slow stops on the last node of the first half
slow, fast = head, next[head]
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
return merge(sort(head), sort(second))
result = []
node = sort(0)
while node != -1:
result.append(values[node])
node = next[node]
return result
易错点和边界情况
- 对整个
values数组排序。第二个示例中加入了9和5，但它们不在列表中。 - 让
fast从头节点开始。只有两个节点时，slow会落在第二个节点上，切分后第二部分为空，递归也就不会缩小。 - 忘记切断
next[slow] = -1。这样第一部分会延伸到第二部分，两个调用会对有重叠的列表排序。 - 另一部分耗尽时，丢弃这一部分的剩余节点。这些节点会从结果中消失。
- 在 Lua 和 R 中，数组从 1 开始：节点索引仍使用从 0 开始的编号，并读取
next[node + 1]。R 版本会复制一次链接数组，因此会额外使用 O(n) 内存。
常见问题3
对链表进行排序的最佳方法是什么？
归并排序。在中间拆分、对两半分别排序并将它们合并，这些操作都沿着列表向前进行，这是单向链表唯一支持的方向。它的时间复杂度为 O(n log n)，并重新连接现有节点。
为什么对于链表，归并排序比快速排序更受青睐？
快速排序可以通过重新连接节点来划分列表，但选择合适的基准值需要随机访问，而将头节点作为基准值会使排序好的列表的时间复杂度达到 O(n²)。归并排序总是将列表一分为二，因此无论输入是什么，时间复杂度都保持为 O(n log n)。
你能否在 O(n log n) 时间和 O(1) 空间内对链表进行排序？
可以，使用自底向上的归并排序。它会将相邻的长度为 1 的有序段合并，然后是长度为 2 的，再然后是长度为 4 的，直到一个有序段覆盖整个列表。共有 log n 次线性遍历，唯一使用的内存是几个节点索引。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def sortList(next, values):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
next = [3, -1, 4, 2, 1] values = [4, 1, 3, 2, 5]
预期输出
[1, 2, 3, 4, 5]