Description
給定一個鏈結串列的頭節點，移除倒數第
n個節點，並回傳頭節點。要求只用一次遍歷完成。
Example:
Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]
Intuition#
核心思路：讓快指針先走 n 步，然後快慢指針同時走，當快指針到底時，慢指針恰好在目標節點的前一個。
- 「倒數第 n 個」等價於「正數第 (length - n + 1) 個」
- 兩次遍歷：先算長度，再找到目標。但題目要求一次遍歷
- 快慢指針間距為 n，當快指針到達尾端，慢指針就在目標前一位
Approaches#
1: Two-Pass (Count Length)#
- 概念: 第一次遍歷計算長度 L，第二次遍歷走到第 (L - n) 個節點進行刪除
- 時間複雜度:
O(n)- 兩次遍歷 - 空間複雜度:
O(1)
class Solution {
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
val dummy = ListNode(0)
dummy.next = head
var length = 0
var curr = head
while (curr != null) {
length++
curr = curr.next
}
curr = dummy
for (i in 0 until length - n) {
curr = curr!!.next
}
curr!!.next = curr.next?.next
return dummy.next
}
}⭐2: One-Pass (Two Pointers)#
- 概念: 使用 dummy head，快指針先走 n+1 步，然後快慢指針同時走，快指針到底時慢指針在目標前一個節點
- 時間複雜度:
O(n)- 只遍歷一次 - 空間複雜度:
O(1)
class Solution {
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
val dummy = ListNode(0)
dummy.next = head
var fast: ListNode? = dummy
var slow: ListNode? = dummy
// 快指針先走 n + 1 步
for (i in 0..n) {
fast = fast?.next
}
// 同時移動直到快指針到底
while (fast != null) {
fast = fast.next
slow = slow?.next
}
// 刪除目標節點
slow?.next = slow?.next?.next
return dummy.next
}
}Dummy head 是關鍵：當要刪除的是第一個節點（n == list length）時，沒有 dummy head 會需要特殊處理。
🔑 Takeaways#
- Pattern: 快慢指針保持固定間距，是解決「倒數第 k 個」類型問題的標準技巧
- 關鍵技巧: Dummy head + 快指針先走 n+1 步（而非 n 步），讓慢指針停在目標的前一個節點，方便刪除操作