目錄

題目

解法一

雙指針算法

核心思想

執行流程

具體例子

代碼

解法二

兩次遍歷法

核心思想

執行流程

具體例子

代碼

---

題目

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

解法一

雙指針算法

核心思想

利用雙指針間隔固定距離(n+1)，當快指針到達鏈表末尾時，慢指針恰好位于倒數第n個節點的前一位置。

執行流程

1. 創建啞節點dummy，指向鏈表頭部
2. 初始化快指針fast和慢指針slow，都指向dummy
3. fast先前進n+1步
4. fast和slow同時前進，直到fast到達NULL
5. slow此時指向待刪除節點的前一節點，執行刪除操作
6. 返回dummy->next作為新的頭節點

具體例子

對于鏈表1→2→3→4→5，刪除倒數第2個節點(n=2)：

1. 創建dummy→1→2→3→4→5
2. fast和slow初始都指向dummy
3. fast前進3步(n+1)：fast指向3
4. fast和slow同時前進：
5. 當fast到達5后的NULL
6. slow指向3
7. 刪除slow->next(即4)：3→5
8. 返回dummy->next：1→2→3→5

代碼

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* fast = dummy;ListNode* slow = dummy;for(int i = 0; i<n+1; i++){if(!fast){return head;}fast = fast->next;}while(fast){fast = fast->next;slow = slow->next;}if(slow->next){ListNode* toDelete = slow->next;slow->next = slow->next->next;delete toDelete;}ListNode* newhead = dummy->next;delete dummy;return newhead;}
};

解法二

兩次遍歷法

核心思想

執行流程

1. 創建啞節點dummy，指向鏈表頭部
2. 第一次遍歷計算鏈表長度length
3. 計算待刪除節點的正序位置：position = length - n
4. 第二次遍歷，前進position步找到待刪除節點的前驅
5. 刪除目標節點
6. 返回dummy->next作為新的頭節點

具體例子

對于鏈表1→2→3→4→5，刪除倒數第2個節點(n=2)：

1. 創建dummy→1→2→3→4→5
2. 計算鏈表長度length?= 5
3. 找到正序位置：position = 5?- 2 = 3
4. 從dummy開始前進3步到達節點3
5. 刪除節點3的下一個節點(4)：3→5
6. 返回dummy->next：1→2→3→5

雙指針法效率更高，因為只需一次遍歷；兩次遍歷法思路更直觀，易于理解。

代碼

ListNode* removeNthFromEnd(ListNode* head, int n) {// 創建啞節點ListNode* dummy = new ListNode(0);dummy->next = head;// 第一次遍歷計算鏈表長度int length = 0;ListNode* first = head;while (first) {length++;first = first->next;}// 計算要刪除節點的位置int position = length - n;// 找到待刪除節點的前一個節點ListNode* curr = dummy;for (int i = 0; i < position; i++) {curr = curr->next;}// 刪除節點并釋放內存ListNode* toDelete = curr->next;curr->next = curr->next->next;delete toDelete;// 獲取新的頭節點head = dummy->next;delete dummy;return head;
}