问题描述
给定一个单链表，将所有偶数节点跟在奇数节点后。注意这里的奇偶指的是节点序号，而不是节点值。
请尝试就地完成，且空间复杂度为 O(1) ，时间复杂度为 O(nodes) 。
栗 1：
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
栗 2：
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
注意：
- 奇数和偶数组中的节点顺序应该和原有顺序保持一致。
- 第一个节点为奇数，第二个节点为偶数，依次类推。
- 链表长度范围在
[0, 10^4]之间。
解题思路
这题最需要注意的一点是：将偶数序号的节点放在奇数序号的节点之后。而不是节点的值，这点刚开始我理解错了，疑惑了好久。
假设原链表如下：
image.png
经过处理后，结果应该是：2->1->3->4。
解法 1
既然要保持节点原有的顺序，那么我们可以逐个遍历节点进行处理。当遇到奇数号节点时（假设序号为 m），将其串到奇数号 m - 2 节点后，同时其前的偶数号 m - 1 与后面的偶数号 m + 1 建立连接，最后奇数号节点 m 与偶数号 m - 1 建立连接。
文字描述有点绕，不太好理解，请看下图：
image.png
这里的操作分为 3 步：
- 奇数 1 号与奇数 3 号相连：将 1 号节点（节点值为 3）与 3 号节点（节点值为1）建立连接。
2->1。 - 偶数 2 号与偶数 4 号相连：将 2 号节点（节点值为 3）与 4 号节点（节点值为 4）建立连接。
3->4。 - 奇数 3 号与偶数 2 号相连：将 3 号节点（节点值为 1）与 2 号节点（节点值为 3）建立连接。
1->3。
js 代码如下：
var oddEvenList = function (head) {
if (head) {
// 指向奇数节点
let p = head;
// 当前节点
let cur = head;
// 前一节点
let pre = null;
// 记录第几个节点
let i = 1;
while (cur) {
if (i % 2 === 1) {
// 非第一个奇数节点
if (pre) {
const next = cur.next;
// 插入到奇数节点后
cur.next = p.next;
p.next = cur;
// 删除 cur
pre.next = next;
// 更新当前节点
cur = next;
// 指向插入的节点
p = p.next;
} else {
pre = cur;
cur = cur.next;
}
} else {
pre = cur;
cur = cur.next;
}
i += 1;
}
}
return head;
};
解法 2
同解法 1 的思路大致相同，只不过在第 3 步时，是在处理完所有节点后，最后建立奇数节点与偶数节点的连接。
处理步骤如下图：
image.png
步骤描述如下：
- 将奇数号节点形成一条链，最后一个节点为 odd。
- 将偶数号节点形成一条链，头结点为 evenHead。
- 将最后的奇数号节点 odd 与偶数号头节点 evenHead 建立连接。
js 代码如下：
var oddEvenList = function (head) {
if (head) {
// 奇数号链最后一个节点
let odd = head
// 偶数号链头
let evenHead = head.next
// 偶数号链最后一个节点
let even = evenHead
while (even) {
// 奇数号进行链接
odd.next = even.next
// 记录最后一个奇数号节点
if (odd.next) {
odd = odd.next
}
// 偶数号进行链接
even.next = odd.next
even = even.next
}
// 奇数号节点与偶数号节点建立连接
odd.next = evenHead
}
return head
}
