Pora的解法和我说的是一回事...
其实可以用一个2n-bit的向量表示2n个元素是否已经包含在某个环里，查找下一个环时从当前位置查找2n-bit的向量，整个过程也是O(n)时间复杂度，不过就是空间复杂度违背题意。

现在还有一种想法是：
1.把A中的a1,a2,...,an翻转，得到A=[an,a(n-1),...,a2,a1,b1,b2,....,b(n-1),bn];
2.取最开头的两个元素和最末尾的两个元素，交换an和b(n-1)，得到A=[b(n-1),a(n-1),A',a(n),b(n)]，交换a(n-1),b(n-1)得到A=[a(n-1),b(n-1),A',a(n),b(n)]
3.递归对A'作第二步所示的处理，最终可以的到A=a(n-1),b(n-1),a(n-3),b(n-3)....a(n-2),b(n-2),a(n),b(n)。这时其实可以将问题转换为一个特殊的in-place merge问题。设ab=a,b;假设此时n为偶数，如果要将A转换为最终形态，需要将A=[ab(n-1)ab(n-3)....ab(1)],[ab(2),ab(4),...,ab(n-2),ab(n)] merge为A=ab(1),ab(2),....,ab(n)。

现在的情况是好像没有O(n)的in-place merge算法，不过这里是个特殊情况，不知道可不可以简化一下