Question:

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

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Thinking:

We need three steps to finish this operation. The first one is to find the middle in the linked list. The second one is to reverse the second half of this linked list. The final one is to link these two parts again.

Solution:

public void reorderList(ListNode head) {
    if (head == null || head.next == null)    return;
    ListNode slow = head, fast = head.next, preMiddle, preCurrent, current, p, q;

    //find the middle
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    //reverse the second half
    preMiddle = slow;
    preCurrent = slow.next;
    while (preCurrent.next != null) {
        current = preCurrent.next;
        preCurrent.next = current.next;
        current.next = preMiddle.next;
        preMiddle.next = current;
    }

    //connect two parts
    p = head;
    q = preMiddle.next;
    while (p != preMiddle) {
        preMiddle.next = q.next;
        q.next = p.next;
        p.next = q;
        p = q.next;
        q = preMiddle.next;
    }

}

Reference:https://leetcode.com/discuss/35599/java-solution-with-3-steps