今天是紀錄LeetCode解題的第十九天

第十九題題目：

給定一個鏈結串列head，從鏈結串列末尾刪除Nth節點，並返回head

解題思路

想刪掉「倒數第 N 個節點」，如果直接正數的方式刪除很麻煩，因為得先知道鏈結串列的長度，所以我們可以利用雙指針的技巧，定義快指針(fast)比慢指針(slow)多走n步，接著快慢指針一起走，直到fast抵達末尾，這時候slow剛好指在「倒數第 N+1 個節點」，所以他的下一個節點，就是要刪除的節點

程式碼

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

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

        while fast.next != None:
            fast = fast.next
            slow = slow.next
        
        slow.next = slow.next.next
        return dummy.next

執行過程

初始狀態

• head = [1,2,3,4,5]
• n = 2
• dummy = fast = slow = dummy → 1 → 2 → 3 → 4 → 5

fast先走n步到節點2

fast、slow一起走

slow最後到節點3指向節點4，最後把slow.next原本指向節點4，跳過去改成指向節點5(slow.next.next)，就成功刪除倒數第n個節點了