Note:

这道题分成三部分，找中点，将Linked List分成两段，翻转第二段，将翻转好的第二段和第一段merge起来。

Key word:

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

class Solution {
    public void reorderList(ListNode head) {
        //corner case
        if (head == null || head.next == null) {
            return;
        }
				// find mid
        ListNode mid = findMiddle(head);
        ListNode one = head;
				// reverse the second part
        ListNode two = reverse(mid.next);
				//de-linked mid
        mid.next = null;
        // merge two part
        while (two != null) {
            ListNode cur = one.next;
            one.next = two;
            one = cur;
            cur = two.next;
            two.next = one;
            two = cur;
        }
    }

    private ListNode findMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

Complexity Analysis:

TC: O(N); 找中点花了O(N)的时间，reverse the second part， 需要 N / 2 的时间， merge two list 同样需要N / 2的时间，overall 是O(N).

SC: O(1);