大家好，我是吴师兄。
三年之期已到，小米汽车，终于要来了！
现在的汽车环境比三年前更加严峻，竞争更加激烈，无论是比亚迪的降价策略还是理想汽车造型的风波，无一不说明商场如战场，市场份额就那么大，必然拼个你死我活。
现在小米汽车入场，机会到底大不大，这个就不是我们能分析出来的了，这个只能看后续的市场反馈，一方面汽车行业竞争很激烈，一方面雷军屡次创业屡次成功的经历太魔幻，两方面一碰撞，说不出哪方占优势。
回到今天的主题，
来看看最近小米笔试的一道算法题
。
这道题目的原型是 LeetCode 上的第 143 号问题：
重排链表
。
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例1:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
示例2：
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
这道题目很考察基本功和观察能力，最终的结果就是将
原
链表的前半部分和原链表的后半部分反转之后的链表进行合并得到的。
所以，需要执行以下三个操作。
1、使用快慢指针寻找链表中点
在链表的头节点设置两个指针 slow、fast，同时将它们向后移动。
每一次，slow 向后移动一步，fast 向后移动两步。
于是，找到了中间节点 5，把链表划分为两个区域。
2、将右边的链表进行反转
3、把这两个区域进行交错合并
属于归并排序的降维版本，这个操作不了解的话可以复习一下
归并排序
。
参考代码如下：
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 重排链表（LeetCode 143）：https://leetcode.cn/problems/reorder-list/
class Solution {
public void reorderList(ListNode head) {
// a、寻找出原链表的中点，把链表划分为两个区域
// b、将右边的链表进行反转
// c、把这两个区域进行交错合并
// 1、使用快慢指针寻找出链表的中点来
// ********
// 对于 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
// 中间节点值为 5
// 所以左边区域为 1 -> 2 -> 3 -> 4 -> 5
// 右边区域为 6 -> 7 -> 8
// 但在视频讲解中，我把 5 归为了右边区域，这是一个错误
// 虽然这个错误并不影响结果，因为合并过程都是一样的逻辑
// ********
ListNode mid = middleNode(head);
// 2、基于 mid 这个中点，将链表划分为两个区域
// 左边的区域开头节点是 head
ListNode leftHead = head;
// 右边的区域开头节点是 mid.next
ListNode rightHead = mid.next;
// 将链表断开，就形成了两个链表了
mid.next = null;
// 3、将右边的链表进行反转
rightHead = reverseList(rightHead);
// 4、将这两个链表进行合并操作，即进行【交错拼接】
while( leftHead != null && rightHead != null){
// 拼接过程如下
// 5、先记录左区域、右区域【接下来将有访问的两个节点】
ListNode leftHeadNext = leftHead.next;
ListNode rightHeadNext = rightHead.next;
// 6、左边连接右边的开头
leftHead.next = rightHead;
// 7、leftHead 已经处理好，移动到下一个节点，即刚刚记录好的节点
leftHead = leftHeadNext;
// 8、右边连接左边的开头
rightHead.next = leftHead;
