LeetCode 143.重排链表

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

1. L0 → L1 → … → Ln - 1 → Ln

复制代码

请将其重新排列后变为：

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

复制代码

不能只是单纯的改背叛点内部的值，而是需要实际的举行节点交换。
思绪：找中点，反转，前后逐一重排

代码：

1. class Solution {
2.     public void reorderList(ListNode head) {
3.         ListNode mid = middleNode(head);
4.         ListNode head2 = reverseList(mid);
5.         while (head2.next != null) {
6.             ListNode nxt = head.next;
7.             ListNode nxt2 = head2.next;
8.             head.next = head2;
9.             head2.next = nxt;
10.             head = nxt;
11.             head2 = nxt2;
12.         }
13.     }
14.     private ListNode middleNode(ListNode head) {
15.         ListNode slow = head, fast = head;
16.         while (fast != null && fast.next != null) {
17.             slow = slow.next;
18.             fast = fast.next.next;
19.         }
20.         return slow;
21.     }
22.     private ListNode reverseList(ListNode head) {
23.         ListNode pre = null, cur = head;
24.         while (cur != null) {
25.             ListNode nxt = cur.next;
26.             cur.next = pre;
27.             pre = cur;
28.             cur = nxt;
29.         }
30.         return pre;
31.     }
32. }

复制代码

性能：
时间复杂度o（n）
空间复杂度o（1）