LCR 021. 刪除鏈表的倒數第 N 個結點 - 力扣（LeetCode）

可以使用雙指針方法來解決這個問題，這樣可以在一次遍歷內完成刪除操作，從而達到 O(n) 的時間復雜度。以下是 Python 代碼實現：

解題思路：

1. 初始化快慢指針：使用兩個指針 fast 和 slow，都指向頭結點。
2. 快指針先走 n 步：這樣當快指針到達鏈表末尾時，慢指針正好指向倒數第 n 個節點的前一個節點。
3. 同時移動快慢指針：直到快指針到達鏈表的末尾。
4. 刪除目標節點：調整前一個節點的 next 指針。

Python 代碼：

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef removeNthFromEnd(head: ListNode, n: int) -> ListNode:dummy = ListNode(0, head)  # 添加啞節點，方便處理邊界情況fast = slow = dummy  # 快慢指針初始化指向啞節點# 讓快指針先走 n+1 步，這樣 slow 指向待刪除節點的前一個節點for _ in range(n + 1):fast = fast.next# 同時移動快慢指針，直到快指針到達鏈表尾部while fast:fast = fast.nextslow = slow.next# 刪除倒數第 n 個節點slow.next = slow.next.nextreturn dummy.next  # 返回真正的頭節點

復雜度分析

• 時間復雜度： O(n)，只遍歷了一次鏈表。
• 空間復雜度： O(1)，只用了常數級額外空間。

示例

# 構造鏈表 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))# 刪除倒數第 2 個節點
new_head = removeNthFromEnd(head, 2)# 打印新鏈表
cur = new_head
while cur:print(cur.val, end=" -> ")cur = cur.next
# 輸出：1 -> 2 -> 3 -> 5 ->

這個方法使用了 啞節點（dummy node），有效地避免了刪除頭節點的特殊情況，使代碼更加簡潔穩健。