给定一个单项链表，要求实现一个算法，把链表分成两部分，前一部分全是下标为偶数的节点，后一部分全是下标为奇数的节点，例如给定链表为下图的第一个队列，要求编写一个算法，将链表转换为第二个队列：
要求算法不能分配多余的内存，同时，在操作链表是，不能更改节点内部的内容，只能更改节点的next 指针。
如果允许分配新内存，那么我们可以先把奇数下标的节点存成一个队列，把偶数下标的节点存成另一个队列，然后把两队列收尾连接即可。但限制条件是不能分配新内存，因此问题的解决需要一点小技巧。
我们可以这么做，用一个指针evenHead,专门指向偶下标节点，用另一个指针,oddHead指向奇下标节点。我们注意到，偶下标节点的下一个节点正好是奇下标节点，同时奇下标节点的下一个节点正好是偶下标节点。因此，如果我们把 evenHead.nex 指向 oddHead.next, oddHead.next 指向evenHead.next ,那么，我们就能实现偶下标节点连在一起，奇下标节点连在一起的效果，例如：
evenHead 指向节点0，oddHead指向节点1， oddHead.next 指向节点2，如果把evenHead的next指针设置成oddHead的next, 那相当于把节点0和2连在一起，然后把evenHead挪到它的next指针指向的节点：
此时evenHead的next指向的是节点3，正好是一个奇下标节点，此时把oddHead的next指向evenHead.next那么就可以实现奇数节点连成一体了：
将上面操作循环下去，直到遍历完整个队列，那么我们的目标就达到了。这个算法没有分配新内存，同时只需对整个链表遍历一次足够，因此算法复杂度是O(n),空间复杂度是O(1).
实现代码如下：
public class EvenOddListSorter {
private Node listHead;
private Node evenHead, oddHead;
public EvenOddListSorter(Node head) {
this.listHead = head;
}
public Node sort() {
if (listHead == null || listHead.next == null) {
return listHead;
}
evenHead = listHead;
oddHead = listHead.next;
Node node = oddHead;
while (evenHead.next != null && oddHead.next != null) {
if (oddHead.next != null) {
evenHead.next = oddHead.next;
evenHead = evenHead.next;
}
if (evenHead.next != null) {
oddHead.next = evenHead.next;
oddHead = oddHead.next;
}
}
evenHead.next = node;
return listHead;
}
}sort函数所实现的正好是我们前面所描述的逻辑。主函数实现如下：
public class LinkList {
public static void main(String[] args) {
ListUtility util1 = new ListUtility();
Node head = util1.createList(10);
EvenOddListSorter sorter = new EvenOddListSorter(head);
head = sorter.sort();
util1.printList(head);
}
}我们先构造一个长度为10的队列，然后对其进行节点的奇偶排序，最后打印出的结果如下：
0 -> 2 -> 4 -> 6 -> 8 -> 1 -> 3 -> 5 -> 7 -> 9 -> null
由此可见，我们算法的实现是正确的。更详细的代码讲解和调试，请参看视频。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
