重新排列奇数和偶数

Question

是否有O（n）算法来重新排列保存顺序的奇数和偶数？辅助数组可以用于中间结果，但重排应该在数组内完成。

我发现这个http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/做需要什么，但它并没有维持秩序

Input: 
1 4 3 8 6 5 7 

Output: 
1 3 5 7 4 8 6 

Answer 1

这个怎么样？

1. 创建两个双向链表（或具有O（1）级联的东西）来分别存储奇数和偶数。
2. 迭代输入列表，将它们分隔到第1步中的列表。
3. 连接两个列表。