【Leetcode】python - [19] Remove Nth Node From End of List 個人解法筆記

題目出處

難度

Medium

題目分類

Linked List, Two Pointers

2026-10-14 三刷

個人範例程式碼 - 三刷 (2026/10/14)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head) # point to head
        slow = fast = dummy # head can be removed
        for _ in range(n+1):
            fast = fast.next # move n+1 first
        while fast:
            slow, fast = slow.next, fast.next # move together to the end

        slow.next = slow.next.next # skip slow.next
        return dummy.next

算法說明

linked list 中，透過 fast, slow 維持固定間距的題目。
這題麻煩的點在於細節處理

新增 dummy 在 head 前面

由於 head 本體也有可能被刪除，所以 dummy 作為如果 head 被刪除時的參考指標。

slow, fast 相對距離是 N + 1

由於最後是透過 fast 指到 None 而停下來，位置是在 n + 1
一開始就必須讓 slow 與 fast 的差距維持在 n + 1

例如：1,2,3,4,5 | n = 2
先補 dummy，並附上 None 作為圖示

dummy(0), 1, 2, 3, 4, 5, None
結束時：fast 位於 None (idx = 6)，slow 要位於 3，才能透過 3.next = 3.next.next 刪除我們的目標 4。
因此開始時：fast 要先走 n + 1 (3) 步

Time Complexity

O(n)

Space Complexity

O(1)

Boundary conditions

留意刪除 head 本人的情況 (透過 dummy 處理)

2022-05-29 二刷

個人範例程式碼 - 二刷 (2022/05/29)

# Definition for singly-linked list.
# class ListNode
# def __init__(self, val=0, next=None)
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if not head:
            return head

        dummy = ListNode(0)
        dummy.next = head
        slow = fast = dummy

        for i in range(n):
            fast = fast.next

        while(fast.next):
            fast = fast.next
            slow = slow.next
        else:
            slow.next = slow.next.next

        return dummy.next

算法說明

使用快慢指針，快慢的間距始終保持 n，
最後當找不到 fast.next (為 None，即最後一個數字時)

做一次「slow.next = slow.next.next」，即可刪除該數字，得到我們要的結果。

input handling

這題 input 有 corner case 要處理，例如 [1], n = 1 的情況。

因此我們使用 dummy = ListNode(0)，並以 dummy.next 作為我們最終的解答。

使用 dummy 的目的，會使得 head 本身是可以刪除的。

Boundary conditions

使用 fast 來控制我們搜尋的範圍。

2021-06-19 一刷

個人解法筆記 (解法重點) - 2021/6/19 一刷

大概念 - TwoPointers

我們可以想像成有兩個指標，一個跑比較快，一個跑比較慢

跑比較快的幫我們去找 head
跑比較慢的幫我們定位要刪除的 node

所以跑比較快的與跑比較慢的會固定間距「n」

正常 case

遍歷停止條件

我們留意最後一個 front 停下來的地方，因為要固定間距 n，
所以當最後搜尋到 front.next 沒有東西時就應該要停下

刪除方法

而刪除的方法，則是靠 back 所在位置的 next 替換成 next.next

你可能會想問為什麼不能在 4 ? ，因為「只有 3 的 next 才能連接到 5」

特殊 case

只有一個值時，front 會跑到空值，所以我們判斷 front 為空，
則回傳 head.next

示意圖

個人範例程式碼 - 一刷 (2021/06/19)

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        back = front = head
        for _ in range(n):
            front = front.next

        if not front:
            return head.next

        while(front.next):
            front, back = front.next, back.next

        # print(back.val)
        back.next = back.next.next
        return head