重新排列一个单链表
一、题目描述
给定一个单链表 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、寻找出原链表的中点，把链表划分为两个区域
2、将右边的链表进行反转
3、把这两个区域进行交错合并
1、使用快慢指针寻找链表中点
在链表的头节点设置两个指针 slow、fast，同时将它们向后移动。
每一次，slow 向后移动一步，fast 向后移动两步。
于是，找到了中间节点 5，把链表划分为两个区域。
2、将右边的链表进行反转
3、把这两个区域进行交错合并
属于归并排序的降维版本，这个操作不了解的话可以复习一下归并排序。
三、参考代码
1、java 代码
// 登录 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; // 9、righthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 righthead = rightheadnext; } } // leetcode 876 : 链表的中间节点 public listnode middlenode(listnode head) { listnode fast = head; listnode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } // leetcode 206 : 反转链表 public listnode reverselist(listnode head) { // 寻找递归终止条件 // 1、head 指向的结点为 null // 2、head 指向的结点的下一个结点为 null // 在这两种情况下，反转之后的结果还是它自己本身 if( head == null || head.next == null) return head; // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点 // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head listnode cur = reverselist(head.next); // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5 // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5 // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点 // 等号右侧为 head，意思就是设置 5 的下一个节点是 4 // 这里出现了两个 next // 第一个 next 是「获取」 head 的下一节点 // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值 head.next.next = head; // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了 // 否则会发生无限循环 head.next = null; // 我们把每次反转后的结果传递给上一层 return cur; }}
2、c++ 代码
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 = nullptr; // 3、将右边的链表进行反转 righthead = reverselist(righthead); // 4、将这两个链表进行合并操作，即进行【交错拼接】 while( lefthead != nullptr && righthead != nullptr){ // 拼接过程如下 // 5、先记录左区域、右区域【接下来将有访问的两个节点】 listnode* leftheadnext = lefthead->next; listnode* rightheadnext = righthead->next; // 6、左边连接右边的开头 lefthead->next = righthead; // 7、lefthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 lefthead = leftheadnext; // 8、右边连接左边的开头 righthead->next = lefthead; // 9、righthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 righthead = rightheadnext; } } listnode* middlenode(listnode* head) { listnode* slow = head; listnode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; }public: listnode* reverselist(listnode* head) { // 寻找递归终止条件 // 1、head 指向的结点为 null // 2、head 指向的结点的下一个结点为 null // 在这两种情况下，反转之后的结果还是它自己本身 if( head == null || head->next == null) return head; // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点 // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head listnode *cur = reverselist(head->next); // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5 // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5 // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点 // 等号右侧为 head，意思就是设置 5 的下一个节点是 4 // 这里出现了两个 next // 第一个 next 是「获取」 head 的下一节点 // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值 head->next->next = head; // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了 // 否则会发生无限循环 head->next = nullptr; // 我们把每次反转后的结果传递给上一层 return cur; } };
3、python 代码
class solution: def reorderlist(self, head: listnode) -> none: # a、寻找出原链表的中点，把链表划分为两个区域 # b、将右边的链表进行反转 # c、把这两个区域进行交错合并 # 1、使用快慢指针寻找出链表的中点来 # ******************************************************* # 对于 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 # 中间节点值为 5 # 所以左边区域为 1 -> 2 -> 3 -> 4 -> 5 # 右边区域为 6 -> 7 -> 8 # 但在视频讲解中，我把 5 归为了右边区域，这是一个错误 # 虽然这个错误并不影响结果，因为合并过程都是一样的逻辑 # ******************************************************* mid = self.middlenode(head) # 2、基于 mid 这个中点，将链表划分为两个区域 # 左边的区域开头节点是 head lefthead = head # 右边的区域开头节点是 mid.next righthead = mid.next # 将链表断开，就形成了两个链表了 mid.next = none # 3、将右边的链表进行反转 righthead = self.reverselist(righthead) # 4、将这两个链表进行合并操作，即进行【交错拼接】 while lefthead and righthead : # 拼接过程如下 # 5、先记录左区域、右区域【接下来将有访问的两个节点】 leftheadnext = lefthead.next rightheadnext = righthead.next # 6、左边连接右边的开头 lefthead.next = righthead # 7、lefthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 lefthead = leftheadnext # 8、右边连接左边的开头 righthead.next = lefthead # 9、righthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 righthead = rightheadnext def middlenode(self, head: listnode) -> listnode: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow def reverselist(self, head): :type head: listnode listnode # 寻找递归终止条件 # 1、head 指向的结点为 null # 2、head 指向的结点的下一个结点为 null # 在这两种情况下，反转之后的结果还是它自己本身 if(head == none or head.next == none): return head # 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点 # 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head cur = self.reverselist(head.next) # 比如原链表为 1 --> 2 --> 3 --> 4 --> 5 # 第一次执行下面代码的时候，head 为 4，那么 head.next = 5 # 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点 # 等号右侧为 head，意思就是设置 5 的下一个节点是 4 # 这里出现了两个 next # 第一个 next 是「获取」 head 的下一节点 # 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值 head.next.next = head # 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了 # 否则会发生无限循环 head.next = none # 我们把每次反转后的结果传递给上一层 return cur
四、复杂度分析
时间复杂度：o(n)，其中 n 是链表中的节点数。
空间复杂度：o(1)。
4G路由器物联网应用实现矿场远程监控与人员管理
对COB和SMD两种小间距LED屏的消毒方式有什么不同之处？
机皇回归！诺基亚8、诺基亚9本月发布：全面屏+骁龙835+蔡司镜头，这才是诺基亚的真正水平！
摩托罗拉首款搭载高通骁龙865 四曲面全面屏
北京5G产业基金正式在北京经济技术开发区设立
重新排列一个单链表
华为张顺茂:迎接拐点,拥抱计算新架构
云矿业公司Coinmint计划在纽约州北部开设比特币采矿工厂
全球首款5G一体化芯片麒麟990芯片本月实现商用
乘用车动力电池系统能量密度创新高 达到191Wh／kg
美国依旧强势 国内无厂半导体份额有提升
张麟：牢牢守住电网安全的大门，奋战在抢修指挥一线
如何实现高速公路变电所的管理
土壤检测仪器厂家有哪些及应用范围
微雪电子AD按键模块简介
FPGA在音乐科技及医疗照护领域的应用
我国陆续出台了很多政策 支持民用无人机的发展
三星电子与丹麦顶级音响公司合作，共同开发下一代显示器
《城市数字孪生标准化白皮书（2022版）》正式发布（附全文下载）
Mentor Graphics获得TSMC 10nm FinFET工艺技术认证
给定一个单链表 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、寻找出原链表的中点，把链表划分为两个区域
2、将右边的链表进行反转
3、把这两个区域进行交错合并
1、使用快慢指针寻找链表中点
在链表的头节点设置两个指针 slow、fast，同时将它们向后移动。
每一次，slow 向后移动一步，fast 向后移动两步。
于是，找到了中间节点 5，把链表划分为两个区域。
2、将右边的链表进行反转
3、把这两个区域进行交错合并
属于归并排序的降维版本，这个操作不了解的话可以复习一下归并排序。
三、参考代码
1、java 代码
// 登录 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; // 9、righthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 righthead = rightheadnext; } } // leetcode 876 : 链表的中间节点 public listnode middlenode(listnode head) { listnode fast = head; listnode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } // leetcode 206 : 反转链表 public listnode reverselist(listnode head) { // 寻找递归终止条件 // 1、head 指向的结点为 null // 2、head 指向的结点的下一个结点为 null // 在这两种情况下，反转之后的结果还是它自己本身 if( head == null || head.next == null) return head; // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点 // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head listnode cur = reverselist(head.next); // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5 // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5 // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点 // 等号右侧为 head，意思就是设置 5 的下一个节点是 4 // 这里出现了两个 next // 第一个 next 是「获取」 head 的下一节点 // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值 head.next.next = head; // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了 // 否则会发生无限循环 head.next = null; // 我们把每次反转后的结果传递给上一层 return cur; }}
2、c++ 代码
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 = nullptr; // 3、将右边的链表进行反转 righthead = reverselist(righthead); // 4、将这两个链表进行合并操作，即进行【交错拼接】 while( lefthead != nullptr && righthead != nullptr){ // 拼接过程如下 // 5、先记录左区域、右区域【接下来将有访问的两个节点】 listnode* leftheadnext = lefthead->next; listnode* rightheadnext = righthead->next; // 6、左边连接右边的开头 lefthead->next = righthead; // 7、lefthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 lefthead = leftheadnext; // 8、右边连接左边的开头 righthead->next = lefthead; // 9、righthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 righthead = rightheadnext; } } listnode* middlenode(listnode* head) { listnode* slow = head; listnode* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; }public: listnode* reverselist(listnode* head) { // 寻找递归终止条件 // 1、head 指向的结点为 null // 2、head 指向的结点的下一个结点为 null // 在这两种情况下，反转之后的结果还是它自己本身 if( head == null || head->next == null) return head; // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点 // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head listnode *cur = reverselist(head->next); // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5 // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5 // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点 // 等号右侧为 head，意思就是设置 5 的下一个节点是 4 // 这里出现了两个 next // 第一个 next 是「获取」 head 的下一节点 // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值 head->next->next = head; // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了 // 否则会发生无限循环 head->next = nullptr; // 我们把每次反转后的结果传递给上一层 return cur; } };
3、python 代码
class solution: def reorderlist(self, head: listnode) -> none: # a、寻找出原链表的中点，把链表划分为两个区域 # b、将右边的链表进行反转 # c、把这两个区域进行交错合并 # 1、使用快慢指针寻找出链表的中点来 # ******************************************************* # 对于 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 # 中间节点值为 5 # 所以左边区域为 1 -> 2 -> 3 -> 4 -> 5 # 右边区域为 6 -> 7 -> 8 # 但在视频讲解中，我把 5 归为了右边区域，这是一个错误 # 虽然这个错误并不影响结果，因为合并过程都是一样的逻辑 # ******************************************************* mid = self.middlenode(head) # 2、基于 mid 这个中点，将链表划分为两个区域 # 左边的区域开头节点是 head lefthead = head # 右边的区域开头节点是 mid.next righthead = mid.next # 将链表断开，就形成了两个链表了 mid.next = none # 3、将右边的链表进行反转 righthead = self.reverselist(righthead) # 4、将这两个链表进行合并操作，即进行【交错拼接】 while lefthead and righthead : # 拼接过程如下 # 5、先记录左区域、右区域【接下来将有访问的两个节点】 leftheadnext = lefthead.next rightheadnext = righthead.next # 6、左边连接右边的开头 lefthead.next = righthead # 7、lefthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 lefthead = leftheadnext # 8、右边连接左边的开头 righthead.next = lefthead # 9、righthead 已经处理好，移动到下一个节点，即刚刚记录好的节点 righthead = rightheadnext def middlenode(self, head: listnode) -> listnode: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow def reverselist(self, head): :type head: listnode listnode # 寻找递归终止条件 # 1、head 指向的结点为 null # 2、head 指向的结点的下一个结点为 null # 在这两种情况下，反转之后的结果还是它自己本身 if(head == none or head.next == none): return head # 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点 # 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head cur = self.reverselist(head.next) # 比如原链表为 1 --> 2 --> 3 --> 4 --> 5 # 第一次执行下面代码的时候，head 为 4，那么 head.next = 5 # 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点 # 等号右侧为 head，意思就是设置 5 的下一个节点是 4 # 这里出现了两个 next # 第一个 next 是「获取」 head 的下一节点 # 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值 head.next.next = head # 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了 # 否则会发生无限循环 head.next = none # 我们把每次反转后的结果传递给上一层 return cur
四、复杂度分析
时间复杂度：o(n)，其中 n 是链表中的节点数。
空间复杂度：o(1)。
4G路由器物联网应用实现矿场远程监控与人员管理
对COB和SMD两种小间距LED屏的消毒方式有什么不同之处？
机皇回归！诺基亚8、诺基亚9本月发布：全面屏+骁龙835+蔡司镜头，这才是诺基亚的真正水平！
摩托罗拉首款搭载高通骁龙865 四曲面全面屏
北京5G产业基金正式在北京经济技术开发区设立
重新排列一个单链表
华为张顺茂:迎接拐点,拥抱计算新架构
云矿业公司Coinmint计划在纽约州北部开设比特币采矿工厂
全球首款5G一体化芯片麒麟990芯片本月实现商用
乘用车动力电池系统能量密度创新高 达到191Wh／kg
美国依旧强势 国内无厂半导体份额有提升
张麟：牢牢守住电网安全的大门，奋战在抢修指挥一线
如何实现高速公路变电所的管理
土壤检测仪器厂家有哪些及应用范围
微雪电子AD按键模块简介
FPGA在音乐科技及医疗照护领域的应用
我国陆续出台了很多政策 支持民用无人机的发展
三星电子与丹麦顶级音响公司合作，共同开发下一代显示器
《城市数字孪生标准化白皮书（2022版）》正式发布（附全文下载）
Mentor Graphics获得TSMC 10nm FinFET工艺技术认证