LeetCode - 19. 删除链表的倒数第 N 个结点

题目

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

思路

使用虚拟头节点（dummy node）：

• 创建一个虚拟头节点并将其next指向原始头节点

• 这样可以统一处理所有情况，包括删除头节点

设置快慢指针：

• 快指针（fast）和慢指针（slow）初始都指向虚拟头节点

快指针先行：

• 让快指针先前进N+1步

• 这样当快指针到达链表末尾时，慢指针正好指向倒数第N个节点的前一个节点

同步移动两个指针：

• 同时移动快慢指针，直到快指针到达链表末尾（即fast为nullptr）

• 此时慢指针指向的是要删除节点的前一个节点

删除节点：

• 执行slow->next = slow->next->next，跳过要删除的节点

• 这样就完成了删除操作

返回新的头节点：

• 返回dummy->next作为新的头节点

• 如果删除的是原始头节点，dummy->next已经更新为新的头节点

这种双指针技巧的优点是：

• 只需要一次遍历就能找到并删除倒数第N个节点

• 不需要事先计算链表长度

• 时间复杂度为O(L)，其中L是链表长度

• 空间复杂度为O(1)，只使用了常数额外空间

读者可能出现的错误写法

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* prev = dummy;ListNode* curr = dummy;for(int i = 0; i< n ; i++){curr = curr->next;}while(curr){prev = prev->next;curr = curr->next;}prev->next = curr;ListNode* newhead = dummy->next;delete dummy;return newhead;}
};

循环前进步数不正确：

   for(int i = 0; i < n; i++) {curr = curr->next;}

这段代码让 curr 指针只前进了 n 步。如果您想删除倒数第 n 个节点，并且 prev 需要指向要删除节点的前一个节点，那么 curr 应该前进 n+1 步。

删除节点的逻辑错误：

   prev->next = curr;

在 while 循环结束后，curr 已经是 nullptr（因为循环条件是 while(curr)）。这行代码实际上是将 prev->next 设置为 nullptr，这意味着它会删除从 prev->next 开始的所有节点，而不仅仅是删除倒数第 n 个节点。

正确的做法是将 prev->next 设置为 prev->next->next，即跳过要删除的节点：

   prev->next = prev->next->next;

正确写法

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