現在介紹有關Linked List的題目，先用簡單的基礎題帶動觀念!
題目連結: 206. Reverse Linked List

題目描述:給你一個單向鏈結串列的頭節點 head，請你反轉整個鏈結串列，並返回反轉後的新頭節點。

Python

鏈結串列是單向的。當我們在節點 2，想要把它的 next 指針指向 1 的時候，我們必須有辦法記住節點 3 的位置，否則後續的鏈結就會「丟失」。關於這類的題型通常需要用到三個指針。

解題思路:

• pre : 指向前一個節點。初始為 None，因為反轉後的第一個節點將指向 None。

• cur : 指向當前正在處理的節點。初始為 head。

• temp : 臨時儲存 cur 的下一個節點，防止鏈結斷裂。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

演算法分析:

• 當cur不為None時，繼續跑while迴圈。
• temp紀錄cur的下一個節點 (防止鏈結丟失的關鍵)。
• 讓當前的值指向它的前值cur.next = pre(例如:1->None)。
• 移動pre至cur的位置。
• 讓cur移動到temp繼續處理。
• 當迴圈結束時，pre 指針正好停在原始鏈結串列的最後一個節點上，也就是反轉後的新頭節點。返回 pre 即可。

流程大概是如下:
初始時:
pre -> None

cur -> [1] -> [2] -> [3] -> None

第一輪迴圈:
cur -> [2] -> [3] -> None

pre -> [1] -> None

第二輪迴圈:
cur -> [3] -> None

pre -> [2] -> [1] -> None

第三輪迴圈:
cur -> None

pre -> [3] -> [2] -> [1] -> None

複雜度分析:

• 時間複雜度為 O(n)(只有遍歷一次鏈結串列，n 是鏈結串列的節點數)。

• 空間複雜度： O(n)(我們只使用了 pre, cur, temp 三個額外的指標變數)。

明天介紹Linked List的變化題
下回見!!