奇偶链表（328）

题目

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例

输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL

输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL

说明

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

算法

双指针

先排除为空链表的情况。

设置奇链表指针odd指向head，偶链表指针even和偶链表头部指针evenHead都指向head.next。此时我们要把链表后面的元素按照奇偶性分别连接到奇链表和偶链表后面：

• 奇链表指针odd的下一位指向偶链表指针的下一位even.next
• 偶链表指针even的下一位指向偶链表指针的下一位的下一位even.next.next
• 奇链表指针odd和偶链表指针even分别指向他们各自的下一位

这样每次奇链表指针和偶链表指针都向后移动，每轮共移动两位，所以我们循环判断需要每次都满足even和even.next存在：

• 当链表总数为偶数时，偶指针even刚好指向链表的最后一位，而且even.next指向null
• 当链表总数为奇数时，奇指针odd指向链表最后一位，偶指针even指向null

最后我们将奇指针odd的下一位指向偶链表的头部evenHead，返回head就是排序后的链表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const oddEvenList = (head) => {
	if (!head) return null;
	let odd = head,
		even = head.next,
		evenHead = head.next;
	while (even && even.next) {
		odd.next = even.next;
		even.next = even.next.next;
		odd = odd.next;
		even = even.next;
	}
	odd.next = evenHead;
	return head;
};