一、題目描述

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

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

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

示例1:

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

示例2：

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

二、題目解析

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

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

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

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

3、把這兩個區(qū)域進行交錯合并

1、使用快慢指針尋找鏈表中點

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

每一次，slow 向后移動一步，fast 向后移動兩步。

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

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

3、把這兩個區(qū)域進行交錯合并

屬于歸并排序的降維版本，這個操作不了解的話可以復習一下歸并排序。

三、參考代碼

1、Java 代碼

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

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

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

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

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

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

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

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

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

ListNoderightHeadNext=rightHead.next;

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

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

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

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

}

}

//LeetCode876:鏈表的中間節(jié)點
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é)點為null
//2、head指向的結(jié)點的下一個結(jié)點為null
//在這兩種情況下，反轉(zhuǎn)之后的結(jié)果還是它自己本身
if(head==null||head.next==null)returnhead;

//不斷的通過遞歸調(diào)用，直到無法遞歸下去，遞歸的最小粒度是在最后一個節(jié)點
//因為到最后一個節(jié)點的時候，由于當前節(jié)點head的next節(jié)點是空，所以會直接返回head
ListNodecur=reverseList(head.next);

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

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


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

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

2、C++ 代碼

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

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

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

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

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

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

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

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

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

ListNode*rightHeadNext=rightHead->next;

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

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

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

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

//不斷的通過遞歸調(diào)用，直到無法遞歸下去，遞歸的最小粒度是在最后一個節(jié)點
//因為到最后一個節(jié)點的時候，由于當前節(jié)點head的next節(jié)點是空，所以會直接返回head
ListNode*cur=reverseList(head->next);

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

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


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

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

}

};

3、Python 代碼

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

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

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

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

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

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

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

#4、將這兩個鏈表進行合并操作，即進行【交錯拼接】
whileleftHeadandrightHead:

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

rightHeadNext=rightHead.next

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

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

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

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

#不斷的通過遞歸調(diào)用，直到無法遞歸下去，遞歸的最小粒度是在最后一個節(jié)點
#因為到最后一個節(jié)點的時候，由于當前節(jié)點head的next節(jié)點是空，所以會直接返回head
cur=self.reverseList(head.next)

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

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

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

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

四、復雜度分析

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

空間復雜度：O(1)。

審核編輯：劉清