【Leetcode 筆記】 206. Reverse Linked List

題目解釋

翻轉 Linked List。

範例

• 輸入: head = [1, 2, 3, 4, 5]
• 輸出: [5, 4, 3, 2, 1]

NOTE：必須是 in-place 的翻轉，不可以把 node 存到某處。

最佳解法

除了初始化 pointer curr 指在 head 以外，我們也要令一個 dummy node 稱為 prev。

每次循環，我們都只翻轉兩個 node: prev 跟 curr，直到 curr 為 None。

步驟

1. 將 curr 所指的下一個 Node 暫存進變數 next_node 中
2. 反轉指標方向，curr 改指向前面的 prev
3. prev 向前進到 curr
4. curr 向前進到 next_node，也就是原先的 curr.next

程式碼

我自己喜歡 iterative 的方式。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head

        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        return prev

理論上 recursive 的比較直覺，總之還是附上 code。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return new_head

時間複雜度

O(n)，其中 n 是 linked list 的長度。因為我們只 traverse 了一次 linked list，每次改 pointer 方向的操作都是 O(1)。

空間複雜度

O(1)，我們基本上沒有用到多餘的地方儲存變數。

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26