这题很简单，不过很容易出bug
特别在merge的时候，所以一定要逻辑清楚，
先写好框架
class Solution {
public void reorderList(ListNode head) {
if (head == null) return ;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode head2 = slow.next;
slow.next = null;
head2 = reverse(head2);
//merge
ListNode cur = new ListNode(0);
while (head != null) {
cur.next = head;
head = head.next;
cur = cur.next;
cur.next = null;
if (head2 == null) break;
cur.next = head2;
cur = cur.next;
head2 = head2.next;
cur.next = null;
}
}
private ListNode reverse(ListNode node) {
if (node == null) return null;
ListNode prev = null;
while (node != null) {
ListNode next = node.next;
node.next = prev;
prev = node;
node = next;
}
return prev;
}
}
