【LeetCode 刷题日】19.删除链表的倒数第n个节点

个人主页北极的代码欢迎来访作者简介java后端学习者评论和❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言继续对链表的学习暴打LeetCode接下来就快到了哈希表其实我在写这些算法之前看过一些关于数据结构的书有的书上来就是摆一堆源码看的迷迷糊糊的有的又太过于简单了目前还没找到很合适的书有没有大佬有推荐的以及一些计算机基础四大件的数据。题目背景LeetCode19给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。进阶你能尝试使用一趟扫描实现吗示例 1输入head [1,2,3,4,5], n 2 输出[1,2,3,5]示例 2输入head [1], n 1 输出[]示例 3输入head [1,2], n 1 输出[1]题目答案class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //新建一个虚拟头节点指向head ListNode dummyNode new ListNode(0); dummyNode.next head; //快慢指针指向虚拟头节点 ListNode fastIndex dummyNode; ListNode slowIndex dummyNode; // 只要快慢指针相差 n 个结点即可 for (int i 0; i n; i) { fastIndex fastIndex.next; } while (fastIndex ! null) { fastIndex fastIndex.next; slowIndex slowIndex.next; } // 此时 slowIndex 的位置就是待删除元素的前一个位置。 // 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解 // 检查 slowIndex.next 是否为 null以避免空指针异常 if (slowIndex.next ! null) { slowIndex.next slowIndex.next.next; } return dummyNode.next; } }题目解析双指针的经典应用如果要删除倒数第n个节点让fast移动n步然后让fast和slow同时移动直到fast指向链表末尾。删掉slow所指向的节点就可以了。思路是这样的但要注意一些细节。这时就有同学不理解为什么快指针要先走n步当然快指针肯定是比慢指针快的从名字就看出来了但具体原理是什么呢简单的来说先走n步就是为了制造快慢指针之间的间距那为什么要制造间距呢首先要明确题目要干嘛要删除倒数第n个节点根据链表的特性我们删除一个节点必须要知道这个节点的前驱节点所以我们做的一切都是为了让慢指针最后停在要删除节点的前置节点那个位置。这样才能slow.next slow.next.next删掉目标节点。因此我们看流程图解为什么快指针要先走 n 步举个最清晰的例子链表1 → 2 → 3 → 4 → 5n 2要删除倒数第 2 个节点 4初始状态plaintextfast slow ↓ 1 → 2 → 3 → 4 → 5 → null① 快指针先走 n 步n2走 2 步plaintextfast slow ↓ ↓ 1 → 2 → 3 → 4 → 5 → null此时快慢相差 n 个节点② 快慢一起走直到 fast 到末尾plaintextfast slow ↓ ↓ 1 → 2 → 3 → 4 → 5 → nullslow 正好停在 3是 4 的前一个③ 删除plaintextslow.next slow.next.next结果1 → 2 → 3 → 5 → null先走 n 步 也就是为了拉开 n 步距离一起走到头 代表着慢指针刚好落在倒数第 n 个的前一个没有这 n 步我们根本定位不到要删的节点因此我们在代码里的for循环就是为了提前让快节点先走n次领先条件理解fast.next ! null的意思是快节点还没走到最后一个节点因为最后一个节点的下一个就是null链表默认的if (slowIndex.next ! null)这里if里面的条件判断是为了防止空指针异常也就是为了防止slow.next.next;空指针关于这里的虚拟头节点我们已经很清楚了它仅仅是为了让头节点与其他的节点平级。结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励