143.重排链表

重排链表

给定一个单链表 L: L0→L1→…→Ln-1→Ln，将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…

解析

找中点 + 反转后半部分 + 合并两个链表。

var reorderList = function (head) {
  let slow = head, fast = head;
  while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }
  let second = slow.next;
  slow.next = null;
  let prev = null;
  while (second) { const next = second.next; second.next = prev; prev = second; second = next; }
  let first = head;
  second = prev;
  while (second) {
    const tmp1 = first.next, tmp2 = second.next;
    first.next = second; second.next = tmp1;
    first = tmp1; second = tmp2;
  }
};