题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

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

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

示例1：

No.143 重排链表 (Medium) - 图1

输入: head = [1,2,3,4]
输出: [1,4,2,3]

示例2：
No.143 重排链表 (Medium) - 图2

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]

思路

将链表拆成两个，l1 和 l2;
将l2翻转；
依次连接两个链表中的结点。

涉及的知识点

如何找到链表中点？

用快慢指针，

如果是奇数个结点，快指针走到末尾的时候，慢指针刚好走到中点；
如果是偶数个结点，快指针走到null的时候，慢指针刚好走到l1的末尾；

链表如何翻转？

递归或者迭代。最好把迭代背下来。

class Solution {
    public void reorderList(ListNode head) {
        // 特殊处理
        // 当结点数小于3时，不用做任何操作，直接返回原链表即可
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        // 注意这里的判断方式，这样子写可以让慢指针最后指向第一个链表的末尾
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode l1 = head;
        // 链表的翻转，可以用递归，不行就用迭代即可。
        ListNode l2 = reverse(slow.next);
        slow.next = null;
        // l1 长度是 大于 l2的，所以l2优先到null
        while (l2 != null) {
            ListNode temp = l2.next;
            l2.next = l1.next;
            l1.next = l2;
            // 精髓在这里
            l1 = l2.next;
            l2 = temp;
        }
    }
    private ListNode reverse(ListNode start) {
        if (start.next == null) {
            return start;
        }
        ListNode l2 = reverse(start.next);
        start.next.next = start;
        start.next = null;
        return l2;
    }
}

注意事项：

快慢指针停止的判断条件：
```
     // 注意这里的判断方式，这样子写可以让慢指针最后指向第一个链表的末尾
     while (fast.next != null && fast.next.next != null) {
         fast = fast.next.next;
         slow = slow.next;
     }
```
之所以不用fast != null && fast.next != null是因为，如果这样判断就会导致最后在停止的时候，慢指针指向了第二个链表的开头，这样不利于我们将链表断开成两个新的链表。可以在纸上画两个例子模拟一下。

理解依次连接两个链表的操作：

     // l1 长度是 大于 l2的，所以l2优先到null
     while (l2 != null) {
         ListNode temp = l2.next;
         l2.next = l1.next;
         l1.next = l2;
         // 精髓在这里
         l1 = l2.next;
         l2 = temp;
     }