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 (Java)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode forward;

    public void reorderList(ListNode head) {
        forward = head;
        dfs(head);
    }

    private void dfs(ListNode node) {
        if (node != null) {
            dfs(node.next);
            if (forward != null) {
                ListNode next = forward.next;
                // even case: forward.next coincide with node
                if (next == node) {
                    node.next = null;
                } else {
                    node.next = next;
                }
                forward.next = node;
                forward = node.next;
            }
            // odd case: forward coincide with node
            if (forward == node) {
                forward.next = null;
                forward = forward.next;
            }
        }
    }
}

Solution (Javascript)

/**
 * 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).