【Leetcode 筆記】19. Remove Nth Node From End of List

題目解釋

給定 linked list 的 head，
從 linked list 的末端刪除第 n 個 node，並回傳其 head。

範例

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

將 linked list 倒數第 2 個元素刪掉並 return head。

最佳解法

很直覺的，可以拆分為三個步驟。

1. 找到 n th 的 node
2. 將 n - 1th 的 next 直接改指到 n + 1th 的 node
3. 快樂 return head

那麼，要怎麼找到 n th 的 node 呢？
又來到了我們的 快慢指針法（Fast-slow Pointers） 出場的時間。

忘記這是什麼或是想溫故知新的朋友，
可以參考 【Leetcode 筆記】143. Reorder List 窩 ~

一個概念各自表述：快慢指針法（Fast-slow Pointers）

之前的所使用到的快慢指針法，
是在一個迴圈裡面同時讓 slow 跟 fast 前進不同步數，
從而讓 slow 到達 linked list 的中間，fast 則先到達末端。

這題的小技巧就在於，我們其實可以先挪動 fast 指針 n 格，
再讓 slow 跟 fast 走到直到 fast 觸底的地方。

假設我們 linked list 的長度是 l，fast 觸底時是第 l 個元素，
而 slow 則會在 l - n 的位置，
slow.next 就會是倒數第 n 個元素 (可以嘗試帶數字進去就知道了)。

程式碼

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow, fast = dummy, dummy

        # let fast move n steps first
        for _ in range(n):
            fast = fast.next

        # let fast move to the linked list end
        while fast.next:
            slow = slow.next
            fast = fast.next

        # slow.next is the <n>th node !
        # <n - 1>th.next -> <n + 1>th node
        #   (slow.next) -> (slow.next.next)
        slow.next = slow.next.next

        return dummy.next

時間複雜度

O(n)，n 是 linked list 的元素個數。

空間複雜度

O(1)，沒有多存東西。

結語

感覺 linked list 相關的題目很多都會要令個 dummy node 保平安呢 ~

• 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