数组 Arr(大小为 n)可以表示双向链表。 [假设细胞有 struct { int val, next, prev; } ]
我在数组中存储了两个列表 A 和 B。 A 有 m 个节点，B 有 n - m 个节点。
这些节点是分散的，我想重新排列它们，使 A 的所有节点都来自 Arr[0] .. Arr[m-1] 和其余节点由 B 的节点填充，时间为 O(m)。
我想到的解决方案是:
- 迭代A直到出现一个位于Arr[m-1]之外的节点
- 然后，迭代B直到出现一个位于Arr[m]之前的节点
- 交换两者(包括操纵它们及其邻居的 next prev 链接)。
但是在这种情况下，迭代的总数是 O(n + m)。因此应该有更好的答案。
附言: 这个问题出现在Introduction to Algorithms, 2nd edition . 习题10.3-5
最佳答案
如何遍历列表 A 并将每个元素放入 Arr[0] ... Arr[m-1] 中，显然将其位置与那里的任何元素交换之前并更新上一个/下一个链接。会有很多交换，但仍然是 O(m)，因为一旦你完成 A 的迭代(m 次迭代)，所有它的元素的一部分将位于(按顺序，顺便说一下)Arr 的前 m 个槽中，因此 B 必须完全位于Arr 的其余部分。
添加一些伪代码
a := index of head of A
for i in 0 ... m-1
swap Arr[i], Arr[a]
a := index of next element in A
end
关于algorithm - 存储 2 个链表的数组中的压缩，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6937430/