合縱連橫: 從鏈結串列應用題 理解 遞回 背後的本質
這篇文章，會帶著大家複習以前學過的遞回框架，
並且鏈結串列的概念與應用為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
遞回框架
- 尋找共通模式(common pattern)，對應到演算法的General case
- 確立初始條件(initial condition)，對應到演算法的Base case
接下來，我們會用這個上面這種框架，貫穿一些同類型，有關聯的題目
(請讀者、或觀眾留意上面的這種 二元搜尋樹 框架，之後的解說會反覆出現)
Reverse Linked List 反轉鏈結串列
這也是一題滿熱門的上機考題目，如果用遞回的角度來看，可以怎麼思考呢?
示意圖
觀察共通的模式
反轉的最小的單元，其實就是兩兩相鄰的節點。
把自己指向前一個節點，
接著用同樣的模式反轉原本的鄰居，也就是下一個節點。
什麼時候停下來呢?
當遞回到空間點(Python裡面就是None)的時候，代表已經處理完所有節點的反轉了。
這時候，返回前一個節點作為反轉後的起始點，作為輸出，也就是最終的答案。
遞回版本的程式碼:
class Solution:
def helper(self, prev, cur):
if cur:
# locate next hopping node
next_hop = cur.next
# reverse direction
cur.next = prev
return self.helper( cur, next_hop)
else:
# new head of reverse linked list
return prev
def reverseList(self, head: ListNode) -> ListNode:
return self.helper( None, head)
Merge Two Sorted Lists 合併兩條已經排序好的鏈結串列
同樣的手法，如果用遞回的角度來看，可以怎麼思考呢?
示意圖
觀察共通的模式
如果第一條的排頭比較小，那麼把第一條的排頭放在前面，接著用同樣的比較合併手法處理第一條的下一個排頭位置 和 第二條。
另一邊對稱的形式
如果第二條的排頭比較小，那麼把第二條的排頭放在前面，接著用同樣的比較合併手法處理第二條的下一個排頭位置 和 第一條。
什麼時候停下來呢?
當其中有一條為空(Python裡面就是None)的時候，剩下的結果由另一條決定。
這題剛好以前有錄過教學影片，提供給讀者作為參考。
遞回版本的程式碼:
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# List 1 is empty, then result is decided by List 2
if not list1:
return list2
# List 2 is empty, then result is decided by List 1
if not list2:
return list1
# General cases: compare node value, and update linkage
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
Swap nodes in Pair 兩兩一組，反轉鏈結串列
這題和Reverse linked list非常像，只是反轉的內部細節稍微改一下，
但是大致上的思考邏輯是雷同的。
如果用遞回的角度來看，可以怎麼思考呢?
示意圖
image.png
觀察共通的模式
反轉的最小的單元，其實就是兩兩相鄰的節點。
把下一個節點指向自己，
接著用同樣的模式反轉下一組pair。
什麼時候停下來呢?
當遞回到空間點(Python裡面就是None) 或者 沒有下一個節點的時候，代表已經處理完所有節點的反轉了。
這時候，返回當初的下一個節點作為反轉後的起始點，作為輸出，也就是最終的答案。
這題剛好以前有錄過教學影片，提供給讀者作為參考。
遞回版本的程式碼:
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
def helper( node ):
# Base case: empty node, or only one node
if not node or not node.next:
return node
# General case:
next_node = node.next
next_pair = next_node.next
# Reverse next node linkage
next_node.next = node
# Update node linkage to next pair
node.next = helper( next_pair)
# return new head after swap
return next_node
# ------------------------------
return helper( head )
結語
好，今天一口氣介紹了最精華的部分，
通用的遞回框架，還有相關的鏈結串列衍伸題與演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
