題目出處

19. Remove Nth Node From End of List

難度

Medium

題目分類

LinkedList, TwoPointers

個人範例程式碼 – 2022/5/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 有 cornet case 要處理，例如 [1], n = 1 的情況。

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

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

Boundary conditions

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

個人解法筆記 (解法重點) – 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

示意圖

個人範例程式碼

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

Reference

• 删除链表中倒数第n个节点 · Remove Nth Node From End of List
• https://leetcode.com/problems/remove-nth-node-from-end-of-list/discuss/8802/3-short-Python-solutions