重新排列一个单链表
一、题目描述
给定一个单链表 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/ classSolution{ publicvoidreorderList(ListNodehead){ //a、寻找出原链表的中点，把链表划分为两个区域 //b、将右边的链表进行反转 //c、把这两个区域进行交错合并 //1、使用快慢指针寻找出链表的中点来 //******************************************************* //对于1->2->3->4->5->6->7->8 //中间节点值为5 //所以左边区域为1->2->3->4->5 //右边区域为6->7->8 //但在视频讲解中，我把5归为了右边区域，这是一个错误 //虽然这个错误并不影响结果，因为合并过程都是一样的逻辑 //******************************************************* ListNodemid=middleNode(head); //2、基于mid这个中点，将链表划分为两个区域 //左边的区域开头节点是head ListNodeleftHead=head; //右边的区域开头节点是mid.next ListNoderightHead=mid.next; //将链表断开，就形成了两个链表了 mid.next=null; //3、将右边的链表进行反转 rightHead=reverseList(rightHead); //4、将这两个链表进行合并操作，即进行【交错拼接】 while(leftHead!=null&&rightHead!=null){ //拼接过程如下 //5、先记录左区域、右区域【接下来将有访问的两个节点】 ListNodeleftHeadNext=leftHead.next; ListNoderightHeadNext=rightHead.next; //6、左边连接右边的开头 leftHead.next=rightHead; //7、leftHead已经处理好，移动到下一个节点，即刚刚记录好的节点 leftHead=leftHeadNext; //8、右边连接左边的开头 rightHead.next=leftHead; //9、rightHead已经处理好，移动到下一个节点，即刚刚记录好的节点 rightHead=rightHeadNext; } } //LeetCode876:链表的中间节点 publicListNodemiddleNode(ListNodehead){ ListNodefast=head; ListNodeslow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } returnslow; } //LeetCode206:反转链表 publicListNodereverseList(ListNodehead){ //寻找递归终止条件 //1、head指向的结点为null //2、head指向的结点的下一个结点为null //在这两种情况下，反转之后的结果还是它自己本身 if(head==null||head.next==null)returnhead; //不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点 //因为到最后一个节点的时候，由于当前节点head的next节点是空，所以会直接返回head ListNodecur=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; //我们把每次反转后的结果传递给上一层 returncur; } }
2、C++ 代码
classSolution{
public:
voidreorderList(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;
}
returnslow;
}
public:
ListNode*reverseList(ListNode*head){
//寻找递归终止条件
//1、head指向的结点为null
//2、head指向的结点的下一个结点为null
//在这两种情况下，反转之后的结果还是它自己本身
if(head==NULL||head->next==NULL)returnhead;
//不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
//因为到最后一个节点的时候，由于当前节点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;
//我们把每次反转后的结果传递给上一层
returncur;
}
};
3、Python 代码
classSolution: defreorderList(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、将这两个链表进行合并操作，即进行【交错拼接】 whileleftHeadandrightHead: #拼接过程如下 #5、先记录左区域、右区域【接下来将有访问的两个节点】 leftHeadNext=leftHead.next rightHeadNext=rightHead.next #6、左边连接右边的开头 leftHead.next=rightHead #7、leftHead已经处理好，移动到下一个节点，即刚刚记录好的节点 leftHead=leftHeadNext #8、右边连接左边的开头 rightHead.next=leftHead #9、rightHead已经处理好，移动到下一个节点，即刚刚记录好的节点 rightHead=rightHeadNext defmiddleNode(self,head:ListNode)->ListNode: slow=fast=head whilefastandfast.next: slow=slow.next fast=fast.next.next returnslow defreverseList(self,head): """ :typehead:ListNode ListNode """ #寻找递归终止条件 #1、head指向的结点为null #2、head指向的结点的下一个结点为null #在这两种情况下，反转之后的结果还是它自己本身 if(head==Noneorhead.next==None): returnhead #不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点 #因为到最后一个节点的时候，由于当前节点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 #我们把每次反转后的结果传递给上一层 returncur
四、复杂度分析
时间复杂度：O(N)，其中 N 是链表中的节点数。
空间复杂度：O(1)。
审核编辑：刘清
声明：本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人，不代表德赢Vwin官网
网立场。文章及其配图仅供工程师学习之用，如有内容侵权或者其他违规问题，请联系本站处理。
举报投诉
-
JAVA
+关注
关注
19文章
2966浏览量
104700 -
python
+关注
关注
56文章
4792浏览量
84626
原文标题：重排链表（LeetCode 143）
文章出处：【微信号：TheAlgorithm，微信公众号：算法与数据结构】欢迎添加关注！文章转载请注明出处。
发布评论请先 登录
相关推荐
约瑟夫环之循环链表这个程序题目大家知道做吗
题目： n个人围成一圈（编号依次为：0,1,2...n-1）,从第一个人开始报数，1，2，……数到m者出列，再从下一个开始重新报数，数到m者再出列……。 下面的程序中，用不带附加表
发表于 10-27 11:08
RT-Thread内核中单链表的使用与实现
1. 链表与数组数组：线性数据结构，存放的数据的类型是一样的，而且他们在内存中的排布是有序排列的。因此数组的优势就是数据连续，随机访问速度快，定义好了就不好在改变大小.单
发表于 04-01 12:01
OpenHarmony中的HDF单链表及其迭代器
成员的值设置成第1个节点的地址。因为单链表只支持往一个方向查找，不支持往回查找，如上面的错误范例。如果root记录的是第二
发表于 08-30 10:31
如何使用EB tresos自动重新排列和计算端口引脚ID？
我指的是修改bootloader的附件文档，只是参考3.4，你能告诉我如何使用EB tresos重新排列和自动计算端口pin ID吗？而且如红圈所指，我对新的端口ID很困惑，GPIO1_6_LED
发表于 03-17 09:03
单链表学习的总结（一）
想必大多数人和我一样，刚开始学数据结构中的单链表还是蛮吃力的，特别是后面的双链表操作更是如此。还有就是在实践代码操作时，你又会感到无从下手，没有思路。
C语言的单链表应用
最近在看一些开源项目，大佬的思路还是很值得去学习，今天就简单介绍一下单链表的应用，配合回调函数可以玩出新花样，废话不多说直接看代码！
工商网监
评论