题目：

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路：找中点，反转，前后逐一重排

代码：

class Solution {public void reorderList(ListNode head) {ListNode mid = middleNode(head);ListNode head2 = reverseList(mid);while (head2.next != null) {ListNode nxt = head.next;ListNode nxt2 = head2.next;head.next = head2;head2.next = nxt;head = nxt;head2 = nxt2;}}private ListNode middleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}private ListNode reverseList(ListNode head) {ListNode pre = null, cur = head;while (cur != null) {ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}return pre;}
}

性能：

时间复杂度o（n）

空间复杂度o（1）