本文转载自微信公众号《程序员熊》，作者Dine。转载本文请联系程序员小熊公众号。本文主要介绍一个面试中经常考到的链表删除相关的题目，即leetcode19.删除链表的最后N个节点。采用双指针+动画的方式进行分析，供大家参考，希望对大家有所帮助。删除链表倒数第N个节点给你一个链表，删除链表倒数第n个节点，返回链表的头节点。进阶：可以尝试用扫描来实现吗？解题思路是在链表中删除一个节点nodeB，首先要找到nodeA，nodeB的上一个节点，然后将nodeA指向nodeC，nodeB的下一个节点，从而实现节点节点B的删除。例如，要删除链表L(1->2->3->4->5)中值为3的节点，首先要找到该节点的前一个节点（与值为2)删除节点，如下图：题目要求删除最后第n个节点，所以首先要找到这个节点的前一个节点，但是因为不知道长度整个链表，你不知道要删除的节点有多少个正节点，所以从头节点开始遍历很难删除这个节点。思路是先遍历链表，获取整个链表的长度；假设整个链表的长度为l，可以知道要删除的节点是第l-n+1个节点；然后再次遍历删除倒数第n个节点。比如链表L是1->2->3->4->5，n=3，那么要删除的节点就是第5-3+1=3个节点。思路2思路1虽然可行，但是需要遍历链表两次，不够简洁，进阶题目中也提到尝试用一次扫描来实现。因此，本文采用双指针的策略，一次扫描删除最后第n个。节点。在上一个链表相关的话题中，虚拟头节点秒杀链表问题提到了添加虚拟头节点解决链表问题的策略。添加虚拟头节点的好处是不需要单独考虑头节点，所以头节点的处理和其他节点一样。本文也采用了这种策略。以链表1->2->3->4->5，n=3为例，如下图。根据上面的分析，先找到倒数第3个节点的前一个节点，也就是值为2的节点；增加虚拟头节点值为2的节点为倒数第4个节点（从后往前），增加两个指针fast/slow，分别指向最后一个元素（NULL）和target在target中的位置上图；此时fast和slow的距离是固定的（n=3），找到目标（slow）后，只需要删除下一个节点，但是如何判断指向的节点前面有多少个节点以缓慢？由于已知fast和slow指向的节点之间的长度是固定的，所以只需要将这两个指针向前移动，直到slow移动到虚拟头节点的位置（值为0），此时fast指向到值为4的节点的位置，fast只需要从虚拟头节点的位置向右移动n+1=4。如下图所示：当fast向右移动到值为4的节点时，指针slow和fast同时向右移动，直到fast移动到NULL。此时slow刚好到达目标位置，即指向倒数第二个n+1节点，如下图所示。给我看看Codec++ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummyHead=newListNode(0);dummyHead->next=head;ListNode*slow=dummyHead,*fast=dummyHead;for(inti=0;i
