1 題目描述

簡單來說，就是給定一個 linked list 和一個數字 n，要求刪除倒數第 n 個節點，並返回新的 linked list。

2 解法

2.1 我的解法

一開始想到的做法:

把所有位置的訊息存在一個 dict 裡面
然後因為已經遍歷過一次知道整個長度，直接尋找到要刪除的節點的前一個進行刪除。


def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    if head.next is None:
        return None

    node_dict = {}
    cur = head
    index = 0
    while cur:
        index += 1
        node_dict.__setitem__(index, cur)
        cur = cur.next

    pre_idx = index - n
    # 有可能指定拿掉 head，就吐 head.next
    if node_dict.get(pre_idx+1) == head:
        head = head.next
        return head
    # 串起來
    pre_node: ListNode = node_dict.get(pre_idx)
    pre_node.next = node_dict.get(pre_idx+2) if node_dict.get(pre_idx+2) else None
    # 斷掉鏈結
    tar_node: ListNode = node_dict.get(pre_idx+1)
    tar_node.next = None
    return head

空間複雜度為 O(n)。
時間複雜度為 O(n)。

如果題目要求 O(1) 這個方法就不行了。

2.2 雙指針

這個方法挺神的，從來沒想過，但是這個方法的時間複雜度為 O(n)，空間複雜度為 O(1)。
這個方法的原理是，我們使用兩個指針，一個是 fast，一個是 slow，fast 比 slow 快 n 個節點，當 fast.next 到達最後一個節點時，slow 就是倒數第 n 個節點的前一個節點，這樣就可以直接刪除了。
我們可以簡單地將兩個指標錯開 n 個節點，方法是在啟動第二個指標（慢速）之前先讓第一個指標（快）先行

大概是這種感覺：

class Solution:
    def removeNthFromEnd2(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:

        slow, fast = head, head

        # 先讓 fast 比 slow 快
        for _ in range(n): fast = fast.next
        # 如果發現是空的，那肯定要拿掉的是第一個node
        if fast is None:
            return head.next

        # 一定是等到 fast node 觸底後停止, 當 fast.next == None 時 slow 在 target 的前一個
        while fast.next:
            fast, slow = fast.next, slow.next

        slow.next = slow.next.next
        return head