给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
输入: head = [1,2,3,4]
输出: [1,4,2,3]
class Solution {
// 从中间一分为二，将后半部分反向，再q
public void reorderList(ListNode head) {
if (head == null) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode left = head;
ListNode right = slow.next;
slow.next = null;
ListNode pre = null;
while (right != null) {
ListNode next = right.next;
right.next = pre;
pre = right;
right = next;
}
right = pre;
while (left != null && right != null) {
ListNode leftNext = left.next;
ListNode rightNext = right.next;
left.next = right;
left = leftNext;
right.next = left;
right = rightNext;
}
}
}