143. Reorder List

Problem

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
  if (!head || !head.next || !head.next.next) return;

  // find mid
  var mid = null;
  var fast = head;
  var slow = head;
  while (fast.next && fast.next.next && slow.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  mid = slow;

  // reverse the later part
  var now = mid.next.next;
  var second = mid.next;
  var tmp = null;
  second.next = null;
  while (now) {
    tmp = now.next;
    now.next = second;
    second = now;
    now = tmp;
  }
  mid.next = second;

  // insert one after another
  var before = head;
  var after = mid.next;
  mid.next = null;
  while (after) {
    tmp = before.next;
    before.next = after;
    before = tmp;
    tmp = after.next;
    after.next = before;
    after = tmp
  }
};

Explain:

比如 1->2->3->4->5->6 ，分三步

1. 找到 mid = 3
2. 翻转后半部分，变成 1->2->3->6->5->4
3. 后半部分依次插入到前半部分

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).