第C++實(shí)現(xiàn)LeetCode(143.鏈表重排序)[LeetCode]143.ReorderList鏈表重排序

GivenasinglylinkedlistL:L0→L1→…→Ln-1→Ln,

reorderitto:L0→Ln→L1→Ln-1→L2→Ln-2→…

Youmaynotmodifythevaluesinthelist'snodes,onlynodesitselfmaybechanged.

Example1:

Given1-2-3-4,reorderitto1-4-2-3.

Example2:

Given1-2-3-4-5,reorderitto1-5-2-4-3.

這道鏈表重排序問(wèn)題可以拆分為以下三個(gè)小問(wèn)題：

1.使用快慢指針來(lái)找到鏈表的中點(diǎn)，并將鏈表從中點(diǎn)處斷開，形成兩個(gè)獨(dú)立的鏈表。

2.將第二個(gè)鏈翻轉(zhuǎn)。

3.將第二個(gè)鏈表的元素間隔地插入第一個(gè)鏈表中。

解法一：

classSolution{

public:

voidreorderList(ListNode*head){

if(!head||!head-next||!head-next-next)return;

ListNode*fast=head,*slow=head;

while(fast-nextfast-next-next){

slow=slow-next;

fast=fast-next-next;

ListNode*mid=slow-next;

slow-next=NULL;

ListNode*last=mid,*pre=NULL;

while(last){

ListNode*next=last-next;

last-next=pre;

pre=last;

last=next;

while(headpre){

ListNode*next=head-next;

head-next=pre;

pre=pre-next;

head-next-next=next;

head=next;

};

我們嘗試著看能否寫法上簡(jiǎn)潔一些，上面的第二步是將后半段鏈表翻轉(zhuǎn)，那么我們其實(shí)可以借助棧的后進(jìn)先出的特性來(lái)做，如果我們按順序?qū)⑺械慕Y(jié)點(diǎn)壓入棧，那么出棧的時(shí)候就可以倒序了，實(shí)際上就相當(dāng)于翻轉(zhuǎn)了鏈表。由于只需將后半段鏈表翻轉(zhuǎn)，那么我們就要控制出棧結(jié)點(diǎn)的個(gè)數(shù)，還好棧可以直接得到結(jié)點(diǎn)的個(gè)數(shù)，我們減1除以2，就是要出棧結(jié)點(diǎn)的個(gè)數(shù)了。然后我們要做的就是將每次出棧的結(jié)點(diǎn)隔一個(gè)插入到正確的位置，從而滿足題目中要求的順序，鏈表插入結(jié)點(diǎn)的操作就比較常見了，這里就不多解釋了，最后記得斷開棧頂元素后面的結(jié)點(diǎn)，比如對(duì)于1-2-3-4，棧頂只需出一個(gè)結(jié)點(diǎn)4，然后加入原鏈表之后為1-4-2-3-(4)，因?yàn)樵谠湵碇薪Y(jié)點(diǎn)3之后是連著結(jié)點(diǎn)4的，雖然我們將結(jié)點(diǎn)4取出插入到結(jié)點(diǎn)1和2之間，但是結(jié)點(diǎn)3后面的指針還是連著結(jié)點(diǎn)4的，所以我們要斷開這個(gè)連接，這樣才不會(huì)出現(xiàn)環(huán)，由于此時(shí)結(jié)點(diǎn)3在棧頂，所以我們直接斷開棧頂結(jié)點(diǎn)即可，參見代碼如下：

解法二：

classSolution{

public:

voidreorderList(ListNode*head){

if(!head||!head-next||!head-next-next)return;

stackListNode*

ListNode*cur=head;

while(cur){

st.push(cur);

cur=cur-next;

intcnt=((int)st.size()-1)/2;

cur=head;

while(cnt--0){

autot=st.top();st.pop();

ListNode*next=cur-next;

cur-next=t;

t-next=next;

cur=next;

st.top()-next=NULL;

};

參考資料：

/problems/reorder-list/

/problems/reorder-list/