題目出處
難度
easy
題目分類
Linked List, Recursion
Linked List reverse 反轉操作 part 3
這邊我們要來研究 Linked list 的 反轉操作，
一樣的，這操作硬要說也不難，但只要思緒不夠清楚，
一定是轉了半天轉不出來XDD 最後絕望放棄XD
我們試著來把概念講的簡單一點吧!
- 這裡作者有找到一個超棒的動畫解釋，有興趣可以看，「真的很讚的動畫」： Easy [C++/Java/Python/JavaScript] Explained+Animated
試試看講簡單一點
做反轉動作來說，最簡單我們都需要「三個紀錄點」，
分別代表「過去」、「現在」、「未來」，
每一個記錄點都非常重要，
我們一定要注意「不能在過程中失去任何重要紀錄點，一旦被蓋掉就再也找不回來了!」
因此我們基本的策略就有了下圖，1 ~ 3，
我們移動的方式一定是：
- - 過去 = 現在
- 現在 = 未來
- 未來 = 更未來
到這邊，「務必務必謹守上述這個原則」，
再來我們再來討論反轉，什麼時候適合做反轉呢?
就是在做上述的「移動 1~3」之前，所以「更改」反轉的線，就是在第 0 步驟，
初始化
這裡有個小重點，不論如何，我們的 Linklist 最終「必須結束於 None」，
因此我們要先宣告個「新結束點」給他，
那想當然，可以讓一開始 prev 擔任這個步驟。
而我們真正作為起頭的 head ，可以先給予他 cur (代表現在)，
由於此時我們還不確定有沒有 head 存在，因此還不能直接給 head.next (會跳錯)
個人範例程式碼
記得上述所說的，我們需要先宣告 None 作為結尾
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None # must have a None end.
if head: # init
cur = head
head = head.next
cur.next = prev # must have a None end.
else: # special case
return head
# loop
while head:
prev = cur
cur = head
head = head.next
cur.next = prev # reverse
return cur
Time Complexity
O(n)
Space Complexity
O(1)
算法說明
遍歷一次 head 是一定要的，問題是我們該怎麼移除，
移除的方法我們上面也提到過了，
只需要把「下個」替換成「下下個」就可以輕鬆解決，
只是要多考慮一些「不存在的邊際情況」，這邊我們下面會提。
corner case 特殊情況處理
一同整理在下方「邊際情況處理」
Boundary conditions/ Edge conditions 邊際情況處理
我們把題目稍微分析一下，我這裡大概把題目分類成於以下三種情況，
- - [None]
- [1]
- [1,2,3] <- 正常情況
其中我們來看看 1.2. 我們該怎麼辦。
1. [None]
如果一開始 if head 就沒東西，我們就直接 return head
2. [1]
我們已經把 cur = head，而 while head 會直接判找不到東西，
因此回傳 cur，沒有問題。