143. 重排链表

解法一：数组

完整遍历链表，用数组存储每个结点的信息。然后从后往前，将后一半的结点插入目标位置，最后将新的尾结点的 next 指针设为 null。

/**
 * 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) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) {
            list.add(p);
        }
        ListNode left = head;
        ListNode right = head.next;
        int len = list.size();
        for (int i = len - 1; i >= (len + 1) / 2; --i) {
            left.next = list.get(i);
            list.get(i).next = right;
            left = right;
            right = right.next;
            //System.out.println(left.val);
            //System.out.println(right.val);
        }
        if ((len & 1) == 1){
            left.next = null;
        } else {
            right.next = null;
        }
    }
}