Linked List 的反轉操作– 陪你刷題

在做linked list 相關題目時，不論是recursive 還是iterative 寫法，寫起來都相當燒腦，因此決定以自己好理解的方式，整理一篇跟linked list 反轉操作 ... 跳至主要內容 在做linkedlist相關題目時，不論是recursive還是iterative寫法，寫起來都相當燒腦，因此決定以自己好理解的方式，整理一篇跟linkedlist反轉操作的文章，作為往後複習來用。

Leetcode#206ReverseLinkedList 遞迴寫法 在開始透過遞迴的方式來反轉linkedlist之前，先回想如何才能使用遞迴，使用遞迴需要滿足以下3個條件： 一個問題的解可以分為幾個子問題的解 這個問題和其子問題除了數據規模不同，求解思路完全一樣 存在遞迴終止條件(basecase) 在思考遞迴問題時，很重要的一點是，絕對不要在腦中想把遞迴一層一層的想清楚，這不符合一般人腦的思考方式！ 單純聚焦於反轉過程中的某一子問題，可以幫助我們思考清楚整個遞迴，如下圖，如果反轉完head→next，接著該怎麼反轉head呢？ 第一步將head→next接往head做到反轉： head->next->next=head; 第二步將head→next指到NULL，至此head節點的前後都被正確反轉。

head->next=NULL; 遞迴問題中，必須定義出終止條件，以反轉linkedlist來說，當走到最後一個節點時後，該節點就不需要再往後處理，而這個節點就會是新的head節點，應該將新頭節點回傳。

掌握以上要點後，遞迴的程式碼也就可以輕鬆寫出。

ListNode*reverseList(ListNode*head) { if(head->next==nullptr) returnhead; ListNode*new_head=reverseList(head->next); head->next->next=head; head->next=NULL; returnnew_head; } 非遞迴寫法 專注於當前節點的反轉即可。

因為反轉操作而喪失連結的節點，需要儲存起來。

classSolution{ public: ListNode*reverseList(ListNode*head){ if(head==nullptr) returnNULL; ListNode*prev=nullptr,*nxt; while(head!=nullptr) { nxt=head->next; head->next=prev; prev=head; head=nxt; } returnprev; } }; Leetcode#92ReverseLinkedListII 此題的input給你[m,n]的區間，要你reverse特定區間內的節點，以下分為遞迴與非遞迴的寫法。

遞迴寫法 我們先從如何reverse前N個節點開始了解。

Reverse前N個節點 與reverse整個linkedlist差別在於： 必須將反轉過後的linkedlist的尾節點（圖中的new_tail或反轉前的head）接往第N+1個節點（圖中的successor或者你要說它是反轉區間最後節點的下一個節點），之前reverse整個linkedlist時候，會將當前的節點的next指向NULL，但這個case下要將當前節點指向第N+1的節點。

遞迴的basecase為當n=1的時候，代表不必再反轉後續節點，但是要將第N+1個節點紀錄下來，並且回傳新的頭節點。

ListNode*successor=nullptr; ListNode*reverseN(ListNode*head,intn) { if(n==1) { successor=head->next; returnhead; } ListNode*new_head=reverseN(head->next,n-1); head->next->next=head; head->next=successor; returnnew_head; } 反轉特定區間節點 知道如何reverse前N個節點後，其實reverse區間[m,n]的節點，等同於我們先前進到第m個節點，就以第m個節點開始來reversen-m個節點即可。

透過遞迴來實作的話，遞迴的basecase即為m=1的時候，回傳反轉後的新頭節點，其他的case下直接將節點一個一個走下去，更新區間的開頭與結束index即可。

ListNode*reverseBetween(ListNode*head,intm,intn) { if(m==1) { returnreverseN(head->next,n); } head->next=reverseBetween(head->next,m-1,n-1); returnhead; } 非遞迴寫法 相比於遞迴寫法，非遞迴更加複雜。

以下圖為例，可以觀察到兩個現象： 反轉區間的前一個節點永遠接往新的頭節點（圖中的new_head) 反轉過後的linkedlist的尾節點（圖中的new_tail）接往反轉區間的後一個節點 只要在每次反轉時把握兩個現象正確，再搭配反轉動作，就可以正確完成反轉區間的任務。

總結一下，每次反轉都會做到以下三樣任務： 反轉區間的前一個節點永遠接往新的頭節點（圖中的new_head) 反轉過後的linkedlist的尾節點（圖中的new_tail）接往反轉區間的後一個節點 反轉兩個節點 另外提一下，這邊使用哨兵節點來處理會更好，可以避免需要特別處理m=1時的特殊狀況。

classSolution{ public: ListNode*reverseBetween(ListNode*head,intm,intn){ ListNode*dummy=newListNode(0),*pre=dummy; dummy->next=head; for(inti=0;inext; } ListNode*new_tail=pre->next; for(inti=0;inext; //現象1 pre->next=new_tail->next; //現象2 new_tail->next=new_tail->next->next; //新一輪的頭節點接往上一輪的頭節點 pre->next->next=temp; } returndummy->next; } }; 這3個任務並沒有一定的先後順序，只要確保每個動作執行完後，所有節點都不會變成孤兒就可以了，以下提供另外一種實作，walker指標用來走訪反轉區間，他走到哪就要反轉到哪。

classSolution{ public: ListNode*reverseBetween(ListNode*head,intm,intn){ if(head==nullptr||head->next==nullptr) returnhead; if(m==n) returnhead; ListNode*dummy=newListNode(0),*prev=dummy; dummy->next=head; for(inti=1;inext; } ListNode*new_tail=prev->next; ListNode*walker=new_tail->next; for(inti=m;inext=walker->next; walker->next=prev->next; prev->next=walker; walker=new_tail->next; } returndummy->next; } }; Leetcode#25ReverseNodesink-Group 每k個節點為一個group進行反轉。

遞迴寫法 這題可以視為#92的進階題。

每次都先走k步確認有足夠多的數量可以進行反轉。

進行反轉後需要將新的head節點回傳回去，以利接起整個linkedlist。

classSolution{ public: ListNode*reverseKGroup(ListNode*head,intk){ if(k==1) returnhead; ListNode*walker=head; for(inti=0;inext; } else { //Ifnumberofleftnodesissmallerthank,justreturn. returnhead; } } ListNode*new_head=reverseN(head,k); head->next=reverseKGroup(walker,k); returnnew_head; } private: ListNode*successor=NULL; ListNode*reverseN(ListNode*head,intk) { if(k==1) { successor=head->next; returnhead; } ListNode*new_head=reverseN(head->next,k-1); head->next->next=head; head->next=successor; returnnew_head; } }; 非遞迴寫法 主要分為兩步驟： 先走訪整個list找出list的總長度。

透過forloop依序swap每個group，已經知道list的總長度，就可以控制總共要swap多少個group。

延伸練習 Leetcode#234,#143 結論 在處理linkedlist問題時，最重要一點就是不要讓任何節點變成孤兒，了解題目後，把題目需要的操作列出來，確認都有執行且執行過程不會讓任何節點變為孤兒，那就可以放心透過遞迴或是iterative的模式操作。

Updatedon2021-05-3010:38:24星期日 文章導覽 上一篇文章上一篇文章:TopKelement–陪你刷題下一篇文章下一篇文章:CS:APP學習筆記 followme linkedin github 近期文章 MaximumSubarraySum問題–陪你刷題 設計一個hashtable–陪你刷題 Leetcode#29DivideTwoIntegers–陪你刷題 Leetcode#647PalindromicSubstrings–陪你刷題 Leetcode#329LongestIncreasingPathinaMatrix–陪你刷題 分類 CS:APP Leetcode linuxkernel 程式設計 自我成長 站內文章搜尋 搜尋關鍵字: 搜尋 彙整 2022年6月 (3) 2022年5月 (6) 2022年1月 (2) 2021年11月 (1) 2021年10月 (2) 2021年9月 (1) 2021年8月 (1) 2021年4月 (2) 2021年3月 (1) 2021年2月 (3) 2021年1月 (5) 2020年12月 (8) 2020年11月 (3) 2020年10月 (1) 2020年9月 (5) 2020年6月 (1) 2019年12月 (1) 2019年10月 (1) 2019年9月 (1) 2019年7月 (1) 2019年6月 (1) 近期文章 MaximumSubarraySum問題–陪你刷題 設計一個hashtable–陪你刷題 Leetcode#29DivideTwoIntegers–陪你刷題 Leetcode#647PalindromicSubstrings–陪你刷題 Leetcode#329LongestIncreasingPathinaMatrix–陪你刷題 分類 CS:APP Leetcode linuxkernel 程式設計 自我成長 近期留言「TopologicalSort–陪你刷題–haogroot'sBlog」於〈Backtracking回溯法–陪你刷題〉發佈留言「Leetcode#329LongestIncreasingPathinaMatrix–陪你刷題–haogroot'sBlog」於〈TopologicalSort–陪你刷題〉發佈留言彙整 2022年6月 2022年5月 2022年1月 2021年11月 2021年10月 2021年9月 2021年8月 2021年4月 2021年3月 2021年2月 2021年1月 2020年12月 2020年11月 2020年10月 2020年9月 2020年6月 2019年12月 2019年10月 2019年9月 2019年7月 2019年6月