Merge Two Sorted Lists
你会得到两个单向链表，它们分别存储在两个长度相同的数组中。在第一个链表中，节点 i 保存值 values1[i]，并链接到节点 next1[i]。第二个链表的处理方式相同，使用 next2 和 values2。在两个链表中，-1 都表示链表结束，头节点都是节点 0。节点并未按链表顺序存储，因此要沿着链接遍历。
每个链表沿着链接按非递减顺序排列。将两个链表合并为一个有序链表，并按顺序返回其中的值。
函数
- next1integer-array
- 第一个列表中每个节点所指向节点的索引；如果是最后一个节点，则为 -1
- values1integer-array
- 第一个列表中每个节点保存的值
- next2integer-array
- 第二个列表中每个节点所链接的节点的索引；末尾节点则为 -1
- values2integer-array
- 第二个列表中每个节点保存的值
- 返回值integer-array
- 合并后列表中的值，按顺序排列
约束条件
1 ≤ L1 ≤ 2000，其中L1是next1和values1的长度。1 ≤ L2 ≤ 2000，其中L2是next2和values2的长度。-1000 ≤ values1[i], values2[j] ≤ 1000-
next1的每个条目都是-1或第一个列表的节点索引，next2的每个条目都是-1或第二个列表的节点索引。 - 从节点
0开始，每个列表都会恰好访问其中的每个节点一次，然后到达-1。不存在循环。 - 沿着其链接，每个列表都按非递减顺序排列。
示例
- 输入
- next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
- 输出
- [1, 2, 3, 4, 6, 7, 9]
- 解释
- 沿着链接，第一个列表访问节点
0, 2, 1，并读取1, 4, 6；第二个列表读取2, 3, 7, 9。每次取较小的首项，得到1, 2, 3, 4, 6, 7, 9。
- 输入
- next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
- 输出
- [-3, 0, 0, 5]
- 解释
- 第一个列表包含
-3, 0, 5，第二个列表只有一个值0。两个0都保留在结果中，所以结果有四个值。
- 输入
- next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
- 输出
- [1, 2, 3, 8, 10]
- 解释
- 第二个列表是
1, 2, 3，这些数都小于第一个列表开头的8。先是整个第二个列表，然后是8, 10。
进阶
你能否在 O(N log k) 时间内合并 k 个有序列表，其中 N 是节点总数？
提示
逐个打开提示，每个都会多透露一点。
两个列表都已经排好序。合并后的列表中，只有哪两个值可能是最小值？
在每个列表的第一个未使用节点上各保留一个指针。两个值中较小的那个节点排在后面，并且只移动对应的指针。一个列表用完后，另一个列表中剩下的所有节点都已经排好序了。
将第二个列表的节点编号接在第一个列表之后，这样一个链接数组就能覆盖两个列表，并在前面添加一个虚拟节点。在合并后列表的最后一个节点上保留一个
tail，将它的链接指向较小的前端节点，然后向前移动。最后，从虚拟节点开始遍历并收集各个值。
题解
两个列表都已排序，因此剩下的最小值始终位于其中一个列表的开头。比较两个列表开头的值，将较小的值链接到结果中，然后向前移动该列表中的位置。对所有 N = L1 + L2 个值进行排序也可以，但这会忽略已有的顺序，且需要 O(N log N) 的时间。
将所有值放入一个数组中并排序
思路
合并后的列表是所有 N 个值排序后的结果，因此要将两个值数组复制到一起并排序。数组中节点的顺序并不重要，因为排序会处理每个值。对于 N ≤ 4000，这种方法足够快，但排序需要进行 O(N log N) 次比较，而合并最多只需要 N-1 次，并且完全不会操作链接，这正是这道题要考查的技能。
算法
- 将
values1和values2复制到一个数组中。 - 按非递减顺序对数组排序。
- 返回它。
def mergeTwoLists(next1, values1, next2, values2):
# Sorting puts every value in its place without following a single link.
return sorted(values1 + values2)将节点拼接到虚拟头节点后面
思路
这里的指针是节点索引。要把两个列表的节点连成一条链，需要给它们统一编号：列表 2 的节点 j 变为节点 L1+j，它的链接也以相同方式偏移。编号为 L1+L2 的虚拟节点位于结果链的前面。
让 a 和 b 分别指向两个列表中尚未使用的第一个节点，让 tail 指向合并链的末尾。每一步都将 tail 链接到较小的首节点，然后让对应的指针和 tail 前进。当一个列表用完时，另一个列表剩余的部分已经有序且已链接好，因此只需一次赋值即可将它接上。在第一个示例中，列表 2 变为节点 3 到 6。处理完节点 0, 3, 6, 2, 1 后，列表 1 已空，link[tail] = 4 会接上 7, 9。
每个节点最多链接一次：时间复杂度为 O(N)。共享链接数组占用 O(N) 内存，而节点对象不需要额外内存。
算法
- 创建一个链接数组：先放入
next1，再放入将next2偏移L1后的值（保留-1不变），最后为虚拟节点L1+L2放入-1。创建对应的值数组。 - 将
a = 0、b = L1和tail设为虚拟节点。 - 当
a和b都不为-1时，将tail链接到较小的那个（相等时选a），然后前移对应的指针，并将tail移到该节点。 - 将
tail链接到a和b中不为-1的那个。 - 从
link[dummy]开始遍历，直到-1，并收集这些值。
def mergeTwoLists(next1, values1, next2, values2):
n1 = len(next1)
n2 = len(next2)
# One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
# dummy that sits in front of the merged list.
link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
value = list(values1) + list(values2)
dummy = n1 + n2
tail = dummy # the last node of the merged list so far
a = 0 # the first unused node of list 1
b = n1 # the first unused node of list 2
while a != -1 and b != -1:
if value[a] <= value[b]:
link[tail] = a # splice a in after the tail
a = link[a]
else:
link[tail] = b # splice b in after the tail
b = link[b]
tail = link[tail]
# One list ran out. The rest of the other one is sorted and linked already.
link[tail] = a if a != -1 else b
merged = []
node = link[dummy]
while node != -1:
merged.append(value[node])
node = link[node]
return merged
易错点和边界情况
- 按索引顺序合并数组。节点的存储顺序是打乱的，所以
values1本身并未排序：在第一个示例中，它是[1, 6, 4]。只有从节点0开始遍历时，顺序才是排好序的。 - 忘记处理剩余元素。当一个列表耗尽时，循环就会停止；如果丢弃另一个列表中剩下的元素，就会丢失最大的值：第一个示例中的
7, 9。 - 移动了错误的指针，或者同时移动了两个指针。你取出哪个列表中的节点，就只移动该列表的指针。
- 混淆了两组编号。列表 2 的节点
2不是列表 1 的节点2。将列表 2 的索引和链接都偏移L1，并保持-1不变。
常见问题3
合并两个已排序列表的时间复杂度是多少？
它是 O(L1 + L2)：每次比较都会放置一个节点，并且不会重复放置任何节点。使用节点对象时，合并只需 O(1) 的额外内存，因为它只会更改链接。使用这里的数组时，共享链接数组需要 O(L1 + L2) 的内存。
合并链表时为什么要使用虚拟节点？
如果没有它，结果中的第一个节点就需要单独编写代码，因为此时还没有尾节点可以将它接在后面。虚拟节点是一个占位头节点，因此第一个节点的链接方式与其他节点相同。最后，返回虚拟节点的下一个节点，占位节点就消失了。
你应该用递归还是迭代的方式合并两个已排序的列表？
递归版本很短：较小的头节点指向其余所有内容的合并结果。但它会为每个节点使用一个栈帧，因此在某些语言中，包含几千个节点的列表可能会导致栈溢出。使用尾指针的迭代循环可以完成相同的工作，而且只占用常量级的栈空间。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def mergeTwoLists(next1, values1, next2, values2):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
next1 = [2, -1, 1] values1 = [1, 6, 4] next2 = [3, 2, -1, 1] values2 = [2, 7, 9, 3]
预期输出
[1, 2, 3, 4, 6, 7, 9]