企业官网建设流程全解析

摘要：本文讲解 LeetCode 第 19 题「删除链表的倒数第 N 个结点」的两种解法。解法一先统计链表长度，再定位并删除目标节点；解法二使用快慢指针，让快指针领先慢指针 n 步后同步移动，从而在一次遍历中完成删除。两种方法均通过虚拟头结点简化边界处理。

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

解法一：大致思路为创建虚拟头结点（有无都可），创建 count 和 while 循环统计链表长度，利用循环for (int i = 0; i < count - n; i++) temp = temp->next;假如 1, 2, 3, 4, 5, n = 2，要删除 4（temp 初始继承 dummy），循环完 temp 指向第三个节点，然后temp->next = temp->next->next;和return dummy->next;即可。

完整代码

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { // 需要返回链表的头结点，也就是说 head 不移动 // 要直接到链表的尾节点，我记得有个函数，是尾指针 ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* current = head; // 结构体指针记录指针指向 ListNode* temp = dummy; int count = 0; // 统计链表长度 while (current) { count++; current = current->next; // 遍历到尾节点 } // if (count == n) // { // return head->next; // } for (int i = 0; i < count - n; i++) { temp = temp->next; } // 循环完以后 temp 里面存储的是第三个节点的位置 // 现在需要获得下一个节点里面 next 的地址 // 指向第四个节点 temp->next = temp->next->next; return dummy->next; } };

解法二：快慢指针法

大致思路：删除的节点为链表第 n 个节点，然后让快指针领先慢指针 n 步，快指针和慢指针间距始终为 n；然后两个再同时移动，循环结束条件是快指针到达最后一个节点，此时慢指针指向要删除的倒数第 n 个节点。因为快慢指针间距不变，最后

slow->next = slow->next->next;

即可。

while (fast->next) { fast = fast->next; slow = slow->next; }

完整代码如下：

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next = head; ListNode* fast = &dummy; ListNode* slow = &dummy; // fast 先走 n 步 for (int i = 0; i < n; i++) { fast = fast->next; } // fast 到最后一个节点之前， // fast 和 slow 一起走 while (fast->next) { fast = fast->next; slow = slow->next; } // 删除 slow 的下一个节点 slow->next = slow->next->next; return dummy.next; } };

如有任何关于文章的建议，感谢各位大佬批评指正😁