算法初学者解决删除链表倒数的节点(力扣19题)(双指针)

1题目介绍在开始之前请理解下图1(仅仅在本题的话链表节点的值不重要所以我的图省去了值)题目要求删除倒数第n个节点。同时链表至少有一个节点n在链表节点数之内2采用方法这里我采用的是双指针法至于为什么我也解释不清先用就行了。3具体逻辑所谓快慢指针肯定要一个快指针和慢指针了。定义在哪里呢先在head节点定义这两位吧。然后请集中注意力争取看一遍就理解.想删除倒数第一个节点就必须要找到倒数第二个节点。想删除倒数第二个节点就必须要找到倒数第三个节点。这是链表删除的知识如果不懂建议了解一下链表删除操作请记住点①想删除倒数第n个节点就要找到倒数第n1个节点。你可能想到了极限情况链表只有一个节点但先忽略后面再提然后是让人头疼的问题单向链表如何找到最后一个节点这不简单吗循环一下不就行了这样确实可以而题目鼓励我们用一次循环就搞定这里我就用第一次循环的思路。想找到最后一个节点最容易想到的方法就是遍历那就这样做但是呢找到最后一个节点的同时顺便把倒数第n1个节点找到这样就能删了。请记住点②快指针找最后一个节点慢指针找倒数第n1个节点(依据点①,找到倒数第n1个就可以删除第n个节点)这时候你就会神奇的发现快慢指针的距离神奇的差了n个节点如下图想删除倒数第2个节点就让slow与fast差了两个节点也就是让快指针提前慢指针走2步请记住点③快指针需要提前慢指针n步综上想要删除第n个节点就要让先快指针领先慢指针n个节点这样似乎就可以写出代码了定义快慢指针于head让快指针提前走n步快慢一起遍历直到快指针找到了最后一个节点此时慢指针就找到了倒数n1个节点就能删除倒数第n个节点了这是题目要求的啊不要忘记题目的要求删除第n个节点返回头结点但是这样写的话就会发现是通过不了的。肯定是遗漏了什么东西没错就是极限情况删除的是链表的头结点此时模拟一下按照之前的思路要删除倒数第n个节点就要让fast指针领先slow指针一步由于slow本身就在头结点上根本找不到头结点前面的节点这怎么删除呢这时候就要引入传说中的虚拟头结点(dummy head)了也不要被吓到这就是一个新的节点你到时候new ListNode一下就行了只是他的名字叫虚拟头结点这个虚拟头结点的一个好处就是方便这种头结点的处理处理如下图现在你再看看呢fast领先慢指针1步这时fast指针不就是最后一个头结点吗slow指针不就是倒数第n1(这个例子中n1也就是112)个节点吗?找到倒数第n1个(倒数第2个)也就是能正确删除倒数第n(倒数第1个)个节点了。这就是引入虚拟头结点的好处。4⚛️题解这样本题两个问题一个主题逻辑和一个极限情况的坑就解决了。写出如下代码(java)class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //定义虚拟头结点用于解决链表只有一个节点的情况 ListNode dummyHeadnew ListNode(); //保存头节点 dummyHead.nexthead; //在dummyhead上定义快慢指针 ListNode fastdummyHead; ListNode slowdummyHead; //让快指针领先n步 while(n--0){ fastfast.next; } //一起移动找到最后的节点 while(fast.next!null){ fastfast.next; slowslow.next; } //删除操作 slow.nextslow.next.next; //返回题目要求的头结点 return dummyHead.next; } }5尾声希望本篇能帮到你本人也是算法初学者如果有错误请在评论区指出谢谢可以给个赞吗这会让博主高兴一整天