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

Solution: O(n) time and O(1) extra space

Steps:

1. find middle of linked list

2. reverse from mid.next to end as right list

3. Merge left list(from head to mid) and right list(end to mid.next)

public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }
    ListNode mid = findMiddle(head);
    ListNode right = mid.next;
    right = reverse(right);
    mid.next = null;
    ListNode left = head;
    ListNode dummyHead = new ListNode(0);
    ListNode runner = dummyHead;
    int count = 0;
    while (left != null && right != null) {
        if (count % 2 == 0) {
            runner.next = left;
            left = left.next;
        } else {
            runner.next = right;
            right = right.next;
        }
        count++;
        runner = runner.next;
    }
    if (left != null) {
        runner.next = left;
    } else {
        runner.next = right;
    }
    head = dummyHead.next;
}

public ListNode reverse(ListNode head) {
    ListNode runner = head;
    ListNode prev = null;
    while (runner != null) {
        ListNode tmp = runner.next;
        runner.next = prev;
        prev = runner;
        runner = tmp;
    }
    return prev;
}

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