/**
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起(还是一条链表)。
 * 请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 * 
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 * 
 * 输入：
 * 1->2->3->4->5->NULL
 * 输出：
 * 1->3->5->2->4->NULL
 */

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

var oddEvenList = function (head) {
  if (head === null) {
    return null
  }
  if (head.next === null) {
    return head
  }
  let odd = head, even = head.next, evenHead = head.next;
  // console.log(evenHead)
  while (even !== null && even.next !== null) {
    odd.next = odd.next.next;
    odd = odd.next;
    even.next = even.next.next;
    even = even.next;
  }
  odd.next = evenHead; // 奇数链表链接偶数链表到最后
  // console.log(evenHead, head.next)
  return head;
};

let node5 = new ListNode(5)
let node4 = new ListNode(4, node5)
let node3 = new ListNode(3, node4)
let node2 = new ListNode(2, node3)
let node1 = new ListNode(1, node2)

console.log(oddEvenList(node1))