在恒定空间中交织数组

Question

我跑过以下样本面试问题.我该如何解决？

假设我们有一个数组a1,a2,...,an,b1,b2,...,bn.

目标是在O(n)时间和O(1)空间中将此数组更改为a1,b1,a2,b2,...,an,bn.换句话说,我们需要一个线性时间算法来修改数组,只需要不超过一定量的额外存储空间.

Answer 1

这个问题并不像人们想象的那样微不足道.家庭作业？大声笑.

以下链接有一个解决方案:http://arxiv.org/abs/0805.1598

Answer 2

如果你能先将数组转换为链表，那么问题就变得微不足道了。