一、題目描述

給定一個(gè)單鏈表 L：L0→L1→…→Ln-1→Ln ，

將其重新排列后變?yōu)椋篖0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

示例1:

給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.

示例2：

給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.

二、題目解析

這道題目很考察基本功和觀察能力，最終的結(jié)果就是將原鏈表的前半部分和原鏈表的后半部分反轉(zhuǎn)之后的鏈表進(jìn)行合并得到的。

所以，需要執(zhí)行以下三個(gè)操作。

1、尋找出原鏈表的中點(diǎn)，把鏈表劃分為兩個(gè)區(qū)域

2、將右邊的鏈表進(jìn)行反轉(zhuǎn)

3、把這兩個(gè)區(qū)域進(jìn)行交錯(cuò)合并

1、使用快慢指針尋找鏈表中點(diǎn)

在鏈表的頭節(jié)點(diǎn)設(shè)置兩個(gè)指針 slow、fast，同時(shí)將它們向后移動(dòng)。

每一次，slow 向后移動(dòng)一步，fast 向后移動(dòng)兩步。

于是，找到了中間節(jié)點(diǎn) 5，把鏈表劃分為兩個(gè)區(qū)域。

2、將右邊的鏈表進(jìn)行反轉(zhuǎn)

3、把這兩個(gè)區(qū)域進(jìn)行交錯(cuò)合并

屬于歸并排序的降維版本，這個(gè)操作不了解的話可以復(fù)習(xí)一下歸并排序。

三、參考代碼

1、Java 代碼

//登錄AlgoMooc官網(wǎng)獲取更多算法圖解
//https://www.algomooc.com
//作者：程序員吳師兄
//代碼有看不懂的地方一定要私聊咨詢吳師兄呀
//重排鏈表（LeetCode 143）：https://leetcode.cn/problems/reorder-list/
classSolution{
publicvoidreorderList(ListNodehead){
//a、尋找出原鏈表的中點(diǎn)，把鏈表劃分為兩個(gè)區(qū)域
//b、將右邊的鏈表進(jìn)行反轉(zhuǎn)
//c、把這兩個(gè)區(qū)域進(jìn)行交錯(cuò)合并

//1、使用快慢指針尋找出鏈表的中點(diǎn)來
//*******************************************************
//對(duì)于1->2->3->4->5->6->7->8
//中間節(jié)點(diǎn)值為5
//所以左邊區(qū)域?yàn)?->2->3->4->5
//右邊區(qū)域?yàn)?->7->8
//但在視頻講解中，我把5歸為了右邊區(qū)域，這是一個(gè)錯(cuò)誤
//雖然這個(gè)錯(cuò)誤并不影響結(jié)果，因?yàn)楹喜⑦^程都是一樣的邏輯
//*******************************************************
ListNodemid=middleNode(head);

//2、基于mid這個(gè)中點(diǎn)，將鏈表劃分為兩個(gè)區(qū)域

//左邊的區(qū)域開頭節(jié)點(diǎn)是head
ListNodeleftHead=head;

//右邊的區(qū)域開頭節(jié)點(diǎn)是mid.next
ListNoderightHead=mid.next;

//將鏈表斷開，就形成了兩個(gè)鏈表了
mid.next=null;

//3、將右邊的鏈表進(jìn)行反轉(zhuǎn)
rightHead=reverseList(rightHead);

//4、將這兩個(gè)鏈表進(jìn)行合并操作，即進(jìn)行【交錯(cuò)拼接】
while(leftHead!=null&&rightHead!=null){

//拼接過程如下
//5、先記錄左區(qū)域、右區(qū)域【接下來將有訪問的兩個(gè)節(jié)點(diǎn)】
ListNodeleftHeadNext=leftHead.next;

ListNoderightHeadNext=rightHead.next;

//6、左邊連接右邊的開頭
leftHead.next=rightHead;

//7、leftHead已經(jīng)處理好，移動(dòng)到下一個(gè)節(jié)點(diǎn)，即剛剛記錄好的節(jié)點(diǎn)
leftHead=leftHeadNext;

//8、右邊連接左邊的開頭
rightHead.next=leftHead;

//9、rightHead已經(jīng)處理好，移動(dòng)到下一個(gè)節(jié)點(diǎn)，即剛剛記錄好的節(jié)點(diǎn)
rightHead=rightHeadNext;

}

}

//LeetCode876:鏈表的中間節(jié)點(diǎn)
publicListNodemiddleNode(ListNodehead){

ListNodefast=head;

ListNodeslow=head;

while(fast!=null&&fast.next!=null){

fast=fast.next.next;

slow=slow.next;
}

returnslow;

}

//LeetCode206:反轉(zhuǎn)鏈表
publicListNodereverseList(ListNodehead){

//尋找遞歸終止條件
//1、head指向的結(jié)點(diǎn)為null
//2、head指向的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為null
//在這兩種情況下，反轉(zhuǎn)之后的結(jié)果還是它自己本身
if(head==null||head.next==null)returnhead;

//不斷的通過遞歸調(diào)用，直到無法遞歸下去，遞歸的最小粒度是在最后一個(gè)節(jié)點(diǎn)
//因?yàn)榈阶詈笠粋€(gè)節(jié)點(diǎn)的時(shí)候，由于當(dāng)前節(jié)點(diǎn)head的next節(jié)點(diǎn)是空，所以會(huì)直接返回head
ListNodecur=reverseList(head.next);

//比如原鏈表為1-->2-->3-->4-->5
//第一次執(zhí)行下面代碼的時(shí)候，head為4，那么head.next=5
//那么head.next.next就是5.next，意思就是去設(shè)置5的下一個(gè)節(jié)點(diǎn)
//等號(hào)右側(cè)為head，意思就是設(shè)置5的下一個(gè)節(jié)點(diǎn)是4

//這里出現(xiàn)了兩個(gè)next
//第一個(gè)next是「獲取」head的下一節(jié)點(diǎn)
//第二個(gè)next是「設(shè)置」當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)為等號(hào)右側(cè)的值
head.next.next=head;


//head原來的下一節(jié)點(diǎn)指向自己，所以head自己本身就不能再指向原來的下一節(jié)點(diǎn)了
//否則會(huì)發(fā)生無限循環(huán)
head.next=null;

//我們把每次反轉(zhuǎn)后的結(jié)果傳遞給上一層
returncur;
}
}

2、C++ 代碼

classSolution{
public:
voidreorderList(ListNode*head){
//a、尋找出原鏈表的中點(diǎn)，把鏈表劃分為兩個(gè)區(qū)域
//b、將右邊的鏈表進(jìn)行反轉(zhuǎn)
//c、把這兩個(gè)區(qū)域進(jìn)行交錯(cuò)合并

//1、使用快慢指針尋找出鏈表的中點(diǎn)來
//*******************************************************
//對(duì)于1->2->3->4->5->6->7->8
//中間節(jié)點(diǎn)值為5
//所以左邊區(qū)域?yàn)?->2->3->4->5
//右邊區(qū)域?yàn)?->7->8
//但在視頻講解中，我把5歸為了右邊區(qū)域，這是一個(gè)錯(cuò)誤
//雖然這個(gè)錯(cuò)誤并不影響結(jié)果，因?yàn)楹喜⑦^程都是一樣的邏輯
//*******************************************************
ListNode*mid=middleNode(head);

//2、基于mid這個(gè)中點(diǎn)，將鏈表劃分為兩個(gè)區(qū)域

//左邊的區(qū)域開頭節(jié)點(diǎn)是head
ListNode*leftHead=head;

//右邊的區(qū)域開頭節(jié)點(diǎn)是mid->next
ListNode*rightHead=mid->next;

//將鏈表斷開，就形成了兩個(gè)鏈表了
mid->next=nullptr;

//3、將右邊的鏈表進(jìn)行反轉(zhuǎn)
rightHead=reverseList(rightHead);

//4、將這兩個(gè)鏈表進(jìn)行合并操作，即進(jìn)行【交錯(cuò)拼接】
while(leftHead!=nullptr&&rightHead!=nullptr){

//拼接過程如下
//5、先記錄左區(qū)域、右區(qū)域【接下來將有訪問的兩個(gè)節(jié)點(diǎn)】
ListNode*leftHeadNext=leftHead->next;

ListNode*rightHeadNext=rightHead->next;

//6、左邊連接右邊的開頭
leftHead->next=rightHead;

//7、leftHead已經(jīng)處理好，移動(dòng)到下一個(gè)節(jié)點(diǎn)，即剛剛記錄好的節(jié)點(diǎn)
leftHead=leftHeadNext;

//8、右邊連接左邊的開頭
rightHead->next=leftHead;

//9、rightHead已經(jīng)處理好，移動(dòng)到下一個(gè)節(jié)點(diǎn)，即剛剛記錄好的節(jié)點(diǎn)
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指向的結(jié)點(diǎn)為null
//2、head指向的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為null
//在這兩種情況下，反轉(zhuǎn)之后的結(jié)果還是它自己本身
if(head==NULL||head->next==NULL)returnhead;

//不斷的通過遞歸調(diào)用，直到無法遞歸下去，遞歸的最小粒度是在最后一個(gè)節(jié)點(diǎn)
//因?yàn)榈阶詈笠粋€(gè)節(jié)點(diǎn)的時(shí)候，由于當(dāng)前節(jié)點(diǎn)head的next節(jié)點(diǎn)是空，所以會(huì)直接返回head
ListNode*cur=reverseList(head->next);

//比如原鏈表為1-->2-->3-->4-->5
//第一次執(zhí)行下面代碼的時(shí)候，head為4，那么head.next=5
//那么head.next.next就是5.next，意思就是去設(shè)置5的下一個(gè)節(jié)點(diǎn)
//等號(hào)右側(cè)為head，意思就是設(shè)置5的下一個(gè)節(jié)點(diǎn)是4

//這里出現(xiàn)了兩個(gè)next
//第一個(gè)next是「獲取」head的下一節(jié)點(diǎn)
//第二個(gè)next是「設(shè)置」當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)為等號(hào)右側(cè)的值
head->next->next=head;


//head原來的下一節(jié)點(diǎn)指向自己，所以head自己本身就不能再指向原來的下一節(jié)點(diǎn)了
//否則會(huì)發(fā)生無限循環(huán)
head->next=nullptr;

//我們把每次反轉(zhuǎn)后的結(jié)果傳遞給上一層
returncur;

}

};

3、Python 代碼

classSolution:
defreorderList(self,head:ListNode)->None:
#a、尋找出原鏈表的中點(diǎn)，把鏈表劃分為兩個(gè)區(qū)域
#b、將右邊的鏈表進(jìn)行反轉(zhuǎn)
#c、把這兩個(gè)區(qū)域進(jìn)行交錯(cuò)合并

#1、使用快慢指針尋找出鏈表的中點(diǎn)來
#*******************************************************
#對(duì)于1->2->3->4->5->6->7->8
#中間節(jié)點(diǎn)值為5
#所以左邊區(qū)域?yàn)?->2->3->4->5
#右邊區(qū)域?yàn)?->7->8
#但在視頻講解中，我把5歸為了右邊區(qū)域，這是一個(gè)錯(cuò)誤
#雖然這個(gè)錯(cuò)誤并不影響結(jié)果，因?yàn)楹喜⑦^程都是一樣的邏輯
#*******************************************************
mid=self.middleNode(head)

#2、基于mid這個(gè)中點(diǎn)，將鏈表劃分為兩個(gè)區(qū)域

#左邊的區(qū)域開頭節(jié)點(diǎn)是head
leftHead=head

#右邊的區(qū)域開頭節(jié)點(diǎn)是mid.next
rightHead=mid.next

#將鏈表斷開，就形成了兩個(gè)鏈表了
mid.next=None

#3、將右邊的鏈表進(jìn)行反轉(zhuǎn)
rightHead=self.reverseList(rightHead)

#4、將這兩個(gè)鏈表進(jìn)行合并操作，即進(jìn)行【交錯(cuò)拼接】
whileleftHeadandrightHead:

#拼接過程如下
#5、先記錄左區(qū)域、右區(qū)域【接下來將有訪問的兩個(gè)節(jié)點(diǎn)】
leftHeadNext=leftHead.next

rightHeadNext=rightHead.next

#6、左邊連接右邊的開頭
leftHead.next=rightHead

#7、leftHead已經(jīng)處理好，移動(dòng)到下一個(gè)節(jié)點(diǎn)，即剛剛記錄好的節(jié)點(diǎn)
leftHead=leftHeadNext

#8、右邊連接左邊的開頭
rightHead.next=leftHead

#9、rightHead已經(jīng)處理好，移動(dòng)到下一個(gè)節(jié)點(diǎn)，即剛剛記錄好的節(jié)點(diǎn)
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指向的結(jié)點(diǎn)為null
#2、head指向的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為null
#在這兩種情況下，反轉(zhuǎn)之后的結(jié)果還是它自己本身
if(head==Noneorhead.next==None):
returnhead

#不斷的通過遞歸調(diào)用，直到無法遞歸下去，遞歸的最小粒度是在最后一個(gè)節(jié)點(diǎn)
#因?yàn)榈阶詈笠粋€(gè)節(jié)點(diǎn)的時(shí)候，由于當(dāng)前節(jié)點(diǎn)head的next節(jié)點(diǎn)是空，所以會(huì)直接返回head
cur=self.reverseList(head.next)

#比如原鏈表為1-->2-->3-->4-->5
#第一次執(zhí)行下面代碼的時(shí)候，head為4，那么head.next=5
#那么head.next.next就是5.next，意思就是去設(shè)置5的下一個(gè)節(jié)點(diǎn)
#等號(hào)右側(cè)為head，意思就是設(shè)置5的下一個(gè)節(jié)點(diǎn)是4

#這里出現(xiàn)了兩個(gè)next
#第一個(gè)next是「獲取」head的下一節(jié)點(diǎn)
#第二個(gè)next是「設(shè)置」當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)為等號(hào)右側(cè)的值
head.next.next=head

#原來的下一節(jié)點(diǎn)指向自己，所以head自己本身就不能再指向原來的下一節(jié)點(diǎn)了
#否則會(huì)發(fā)生無限循環(huán)
head.next=None

#我們把每次反轉(zhuǎn)后的結(jié)果傳遞給上一層
returncur

四、復(fù)雜度分析

時(shí)間復(fù)雜度：O(N)，其中 N 是鏈表中的節(jié)點(diǎn)數(shù)。

空間復(fù)雜度：O(1)。

審核編輯：劉清