# Reorder List

Given a singly linked list _L_: _&#x4C;_&#x30;→_&#x4C;_&#x31;→…→_Ln_-1→_&#x4C;_&#x6E;,\
reorder it to: _&#x4C;_&#x30;→_Ln_→_&#x4C;_&#x31;→_Ln_-1→_&#x4C;_&#x32;→_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.
```

```java
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;
        }
    }
}
```
