重新排列一個單鏈表

一、題目描述

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

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

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

示例1:

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

示例2：

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

二、題目解析

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

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

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

2、將右邊的鏈表進行反轉

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

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

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

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

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

2、將右邊的鏈表進行反轉

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、將右邊的鏈表進行反轉
//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ū)域，這是一個錯誤
//雖然這個錯誤并不影響結果，因為合并過程都是一樣的邏輯
//*******************************************************
ListNodemid=middleNode(head);

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

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

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

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

//3、將右邊的鏈表進行反轉
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:反轉鏈表
publicListNodereverseList(ListNodehead){

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

//不斷的通過遞歸調用，直到無法遞歸下去，遞歸的最小粒度是在最后一個節(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，意思就是去設置5的下一個節(jié)點
//等號右側為head，意思就是設置5的下一個節(jié)點是4

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


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

//我們把每次反轉后的結果傳遞給上一層
returncur;
}
}

2、C++ 代碼

classSolution{
public:
voidreorderList(ListNode*head){
//a、尋找出原鏈表的中點，把鏈表劃分為兩個區(qū)域
//b、將右邊的鏈表進行反轉
//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ū)域，這是一個錯誤
//雖然這個錯誤并不影響結果，因為合并過程都是一樣的邏輯
//*******************************************************
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、將右邊的鏈表進行反轉
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指向的結點為null
//2、head指向的結點的下一個結點為null
//在這兩種情況下，反轉之后的結果還是它自己本身
if(head==NULL||head->next==NULL)returnhead;

//不斷的通過遞歸調用，直到無法遞歸下去，遞歸的最小粒度是在最后一個節(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，意思就是去設置5的下一個節(jié)點
//等號右側為head，意思就是設置5的下一個節(jié)點是4

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


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

//我們把每次反轉后的結果傳遞給上一層
returncur;

}

};

3、Python 代碼

classSolution:
defreorderList(self,head:ListNode)->None:
#a、尋找出原鏈表的中點，把鏈表劃分為兩個區(qū)域
#b、將右邊的鏈表進行反轉
#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ū)域，這是一個錯誤
#雖然這個錯誤并不影響結果，因為合并過程都是一樣的邏輯
#*******************************************************
mid=self.middleNode(head)

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

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

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

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

#3、將右邊的鏈表進行反轉
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指向的結點為null
#2、head指向的結點的下一個結點為null
#在這兩種情況下，反轉之后的結果還是它自己本身
if(head==Noneorhead.next==None):
returnhead

#不斷的通過遞歸調用，直到無法遞歸下去，遞歸的最小粒度是在最后一個節(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，意思就是去設置5的下一個節(jié)點
#等號右側為head，意思就是設置5的下一個節(jié)點是4

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

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

#我們把每次反轉后的結果傳遞給上一層
returncur

四、復雜度分析

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

空間復雜度：O(1)。

審核編輯：劉清