Lt328. 奇偶链表

328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 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(N)，时间复杂度 O(2*nodes)。
遍历一次，存储奇数偶数节点的值到奇数偶数数组中。再遍历一次，修改链表节点的值。

遍历一次+无额外空间

设置一个 o 指向奇数节点，e 指向偶数节点，temp 指向第一个偶数节点用于记录第偶数节点链表。遍历一次链表：

1. 先将奇数节点的 next 指向偶数节点的 next 即下一个奇数节点，就将两个奇数节点连接到了一起，再令 o 指向 o.next。
2. 然后将 e 的 next 指向 o 的 next，即将该节点连接上了第二个偶数节点，再令 e 指向 e.next。

循环以上过程，遍历完成以后，分别形成了奇数和偶数的两条链表。将奇数节点链表的最后一个指向 temp，即连接上奇数和偶数链表。

解答

额外数组+遍历两次

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function (head) {
  let p = head,
    count = 1;
  const oArr = [],
    eArr = [];
  while (p) {
    if (count % 2 === 0) {
      eArr.push(p.val);
    } else {
      oArr.push(p.val);
    }
    count++;
    p = p.next;
  }
  p = head;
  while (p) {
    if (oArr.length) {
      p.val = oArr.shift();
    } else {
      p.val = eArr.shift();
    }
    p = p.next;
    count++;
  }
  return head;
};

遍历一次+无额外空间

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function (head) {
  if (!head) return head;
  let o = head,
    e = o.next,
    temp = e;
  while (o && o.next && e && e.next) {
    o.next = e.next;
    o = o.next;
    e.next = o.next;
    e = e.next;
  }
  o.next = temp;
  return head;
};