Reorder List

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.

class Solution {
    public ListNode reverse(ListNode node) {
        ListNode prev = null, temp = node;
        while (temp != null) {
            ListNode t = temp.next;
            temp.next = prev;
            prev = temp;
            temp = t;
        }
        return prev;
    }

    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode rightSide = reverse(slow.next);
        slow.next = null;
        ListNode leftSide = head;
        while (leftSide != null && rightSide!=null) {
            ListNode temp1 = leftSide.next;
            ListNode temp2 = rightSide.next;
            leftSide.next = rightSide;
            rightSide.next = temp1;
            leftSide = temp1;
            rightSide = temp2;
        }
    }
}