[LeetCode解題攻略] 19. Remove Nth Node From End of List

題目描述

給定一個Linked list的head，從這個Linked list的末尾刪除第 n 個節點並返回其head。

範例 1：

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

範例 2：

Input: head = [1], n = 1
Output: []

範例 3：

Input: head = [1,2], n = 1
Output: [1]

解題思路

該題要求移除倒數第 n 個節點，需要確保遍歷Linked list不超過一次（若可能），以提升效率。

主要解題思路有兩種：

1. 雙遍歷法：
2. • 第一次遍歷計算Linked list的總長度。
   • 第二次遍歷找到需要刪除的節點並移除它。
2. 雙指針法：
3. • 使用兩個指針 fast 和 slow，fast 先行移動 n 步，然後兩指針同步移動，直到 fast 到達尾部。此時，slow 停在要刪除節點的前一個節點。

解法一：雙遍歷法

思路

1. 第一遍遍歷：計算Linked list總長度 L。
2. 第二遍遍歷：找到從頭部數過來的第 L-n+1 個節點並移除它。
3. 特殊情況處理：如果刪除的是頭節點，直接返回 head.next。

實現 (Python)

# 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]:
        # 建立虛擬節點，方便處理頭節點被刪除的情況
        dummy = ListNode(0, head)
        length = 0
        current = head

        # 第一次遍歷：計算鏈表長度
        while current:
            length += 1
            current = current.next

        # 計算從頭部開始的目標位置
        target = length - n
        current = dummy

        # 第二次遍歷：到達目標節點的前一個節點
        for _ in range(target):
            current = current.next

        # 刪除目標節點
        current.next = current.next.next

        return dummy.next

時間與空間複雜度

• 時間複雜度：O(L)，其中 L 是Linked list的長度，需要遍歷兩次Linked list。
• 空間複雜度：O(1)，不需要額外空間。

解法二：雙指針法

思路

1. 使用兩個指針 fast 和 slow：
2. • fast 先移動 n 步。
   • 然後同時移動 fast 和 slow，直到 fast 到達Linked list尾部。
2. 此時，slow 位於要刪除節點的前一個節點。
3. 特殊情況處理：如果刪除的是頭節點，直接返回 head.next。

實現 (Python)

# 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]:
        # 建立虛擬節點，方便處理頭節點被刪除的情況
        dummy = ListNode(0, head)
        fast = dummy
        slow = dummy

        # 讓 fast 指針先移動 n+1 步
        for _ in range(n + 1):
            fast = fast.next

        # 讓 fast 和 slow 同時移動，直到 fast 到達末尾
        while fast:
            fast = fast.next
            slow = slow.next

        # 刪除目標節點
        slow.next = slow.next.next

        return dummy.next

時間與空間複雜度

• 時間複雜度：O(L)，其中 L 是Linked list的長度，僅需一次遍歷。
• 空間複雜度：O(1)，不需要額外空間。

總結

建議優先掌握雙指針法，因其效率較高且應用範圍廣。熟悉這類方法後，對解決其他類似問題（如 Linked List Cycle 或 Find Middle of Linked List）也會更有幫助！