143. Reorder List

using Stack to save all list data, then pop, to insert in original list, but has to remove cycle at last.

T: O(n)

S: O(n)

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode newHead = head;
        while (newHead != null) {
            stack.push(newHead);
            newHead = newHead.next;
        }

        int n = stack.size();
        newHead = head;
        for (int i = 0; i < n/2; i++) {
            ListNode temp = newHead.next;
            newHead.next = stack.peek();
            stack.pop().next = temp; // when even, point to itself like 1 4 2 3, 的 3
            newHead = newHead.next.next;
        }
        newHead.next = null; // remove last cycle
    }
}

/***
3
1 4 2 3
      x

4
3
2
1


1 5 2 4 3

1 5 2 4 3


4
3
2
1

1 5 2 4

 */
```