摘要本文讲解 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要删除 4temp 初始继承 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; } };如有任何关于文章的建议感谢各位大佬批评指正
