奇偶链表问题
作者：Grey
原文地址：
题目描述
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。
你的算法的空间复杂度应为 O(1)，
时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明: 应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
主要思路
如果用辅助数组来做，非常简单，但是不满足题目的要求，因为题目要求空间复杂度 O(1)，意味着不能额外申请辅助数组，换一个思路，考虑用一个整型变量来记录遍历的位置是奇数还是偶数，然后用四个指针分别记录当前奇数链表的开头，结尾；偶数链表的开头和结尾，最后把两个链表串联起来即可，所以，只需要设置五个变量即可完成整个算法。
// 奇数链表的开头节点
ListNode oddStart = null;
// 奇数链表的结尾节点
ListNode oddEnd = null;
// 偶数链表的开头节点
ListNode evenStart = null;
// 偶数链表的结尾节点
ListNode evenEnd = null;
// 当前遍历到的节点
ListNode cur = head;
// 当前遍历到的位置，根据题目意思，从 1 开始
int count = 1;
整个流程如下，遍历 cur 指针，同步记录 count，如果 count 记录的位置是奇数， 则构造奇数链表，如果 count 位置记录的是偶数，则构造偶数链表。
构造的过程也比较简单，以构造奇数链表为例：
如果 oddStart 变量为空，则说明奇数链表未初始化，则直接初始化
oddStart = cur;
oddEnd = cur;
奇数链表的头尾指针都指向 cur，说明初始化完成；
否则，说明奇数链表已经初始化过，则把奇数链表的尾部的 next 直接连上 cur，然后把奇数链表的尾部指针指向 cur,即
oddEnd.next = cur;
oddEnd = cur;
构造偶数链表的过程和构造奇数链表的过程同理，不赘述。
构造好两个链表以后，把两个链表连接起来即可，连接的逻辑如下：
如果偶数链表尾部不为空，则奇数链表一定不为空，且偶数链表的尾部就是变换后链表的尾部，即
if (evenEnd != null) {
evenEnd.next = null;
}
最后，要把奇数链表尾部的 next 连接上偶数链表的头部
oddEnd.next = evenStart;
完整代码如下
class Solution {
// 奇数节点和偶数节点放在一起
// 所有偶数下标的数一定要在奇数下标数之后（注意：是下标而非值）
public static ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return head;
}
ListNode oddStart = null;
ListNode oddEnd = null;
ListNode evenStart = null;
ListNode evenEnd = null;
ListNode cur = head;
int count = 1;
while (cur != null) {
if ((count & 1) == 1) {
// 奇数
if (oddStart == null) {
oddStart = cur;
} else {
oddEnd.next = cur;
}
oddEnd = cur;
} else {
// 偶数
if (evenStart == null) {
evenStart = cur;
} else {
evenEnd.next = cur;
}
evenEnd = cur;
}
count++;
cur = cur.next;
}
if (evenEnd != null) {
evenEnd.next = null;
}
oddEnd.next = evenStart;
return oddStart;
}
}