给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[1,4,2,3]示例 2：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]提示：
- 链表的长度范围为
[1, 5 * 104] 1 <= node.val <= 1000
解题思路
这道题如果我们直接重排的话，那么时间复杂度比较高，并且程序也比较复杂，所以我们要分解问题来分析！
仔细想想，这道题无非就是让链表从头和从末尾开始每一个节点进行合并，那不就相当于是两个链表的合并操作吗对不对！并且其中一个链表就是原链表中的前半部分，另一个链表是原链表中后半部分的逆序，比如例子中的 1->2->3->4->5，前半部分可以看作是 1->2->3（这道题也可以看作是 1->2，最后合并结果都是一样的），后半部分则是逆序的情况：5->4，此时将它们逐个合并起来就是 1->5->2->4->3 了！
根据上面的解析，我们可以把这道题分为三步来解决：
- 找到链表的中间节点（使用快慢指针就能得到，此时
slow就是中间节点） - 逆序中间节点的右侧链表（可以使用双指针或者头插法，下面再讨论）
- 合并左右两个链表
上面的操作我们都是耳熟能详啦，其中要注意的无非就是第二步，这里介绍头插法的使用，其实就是引入一个新的头节点 newhead，将右侧链表中的节点逐个头插到 newhead 后面，最后得到一个只有后半部分的逆序链表，而原链表中就剩下前半部分！只不过要注意一些细节，下面我们来讨论一下！（至于双指针的做法，这里就不介绍了，其实相对头插法来说没那么好理解！）
因为链表的个数可以为奇数或者是偶数，所以我们要考虑一下中间节点 slow 是否要包括在头插法和逆序的操作中，所以此时我们使用头插法的时候有两种策略：
-
将中间节点
slow后面的链表进行逆序，包括中间节点slow：-
其实这种情况下无论是链表个数是奇数还是偶数的话，使用头插法的时候都不太好整，因为可能会出现一些
bug，如下图所示：
-
因为我们最后是要将后半部分单独拎出来作为一个逆序链表，但是此时有一个问题，就是
slow前面的节点的next是指向slow的，因为我们要断开左右部分的链接，此时需要将其slow前面的节点的next置为空，不然在后面合并遍历的时候，就会死循环。但问题是这是一个单链表，要找到前面的节点的话势必要重新遍历，时间复杂度就提高了，所以这种包括中间节点的也一起头插和逆序的操作是不推荐的，不如使用下面的策略！
-
-
将中间节点
slow后面的链表进行逆序，但不包括中间节点slow：-
此时这种情况就比较好办了，无论链表的个数是奇数还是偶数，此时中间节点最后都不属于右半部分的，而是属于前半部分的，那么同样两个链表要断开连接的话，就在中间节点
slow断开，这就非常简单了，直接就是一个slow->next = nullptr就解决了，非常的高效和简单！
-
比如举个例子，如下图所示：
-
此外需要注意的细节就是，在进行逆序头插法的时候，需要先记录一下当前节点的下一个节点，防止指向改变后丢失，其它就没有什么大问题了！
解决了第二步，那么第三步就没问题了，就是要将右侧链表的每个节点插入到左侧链表的每个节点中！下面直接给出代码，具体过程可以结合自己画图来分析，都是不难的，只是流程多而已
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
// 1. 找到链表的中间节点
ListNode* fast = head;
ListNode* slow = head;
while(fast != nullptr && fast->next != nullptr)
{
slow = slow->next;
fast = fast->next->next;
}
// 2. 逆序中间节点之后的链表，但不包括中间节点（此时slow就是中间节点）
ListNode* newhead = new ListNode(0, nullptr);
ListNode* right = slow->next;
while(right != nullptr)
{
ListNode* next = right->next; // 先记录下一个节点防止丢失
right->next = newhead->next;
newhead->next = right;
right = next;
}
// 3. 合并左右两个链表
slow->next = nullptr; // 记得要断开左右链表的连接，不然会死循环
ListNode* cur1 = head;
ListNode* cur2 = newhead->next;
while(cur1 != nullptr && cur2 != nullptr)
{
ListNode* next1 = cur1->next;
ListNode* next2 = cur2->next;
cur1->next = cur2;
cur2->next = next1;
cur1 = next1;
cur2 = next2;
}
delete newhead; // 别忘了要释放节点
}
};