本文主要介绍一道面试中常考链表删除相关的题目，即 leetcode 19. 删除链表的倒数第 N 个结点。采用 双指针 + 动图 的方式进行剖析，供大家参考，希望对大家有所帮助。
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
解题思路
在链表中要删除某个节点 nodeB，必须先找到 该节点的前一节点 nodeA ，再将 nodeA 指向 nodeB 的下一节点 nodeC ，从而实现节点 nodeB 的删除。
例如要删除链表 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 个节点 。
思路二
尽管思路一可行，但是需要 遍历链表两遍，不够简洁，而且题目的 进阶 中也提到尝试使用一趟扫描实现，因此本文采用 双指针 的策略，实现通过一次扫描删除 倒数第 n 个节点 。
在上一期链表相关专题 虚拟头节点秒杀链表问题 中提到 增加虚拟头节点 的策略解决链表问题，增加虚拟头节点的 好处 在于：不需要单独考虑头节点，这样对头节点的处理就像跟其它节点一样。本文也同样采用这种策略。
举栗
以链表 1->2->3->4->5，n = 3 为栗，如下如示。
按照上面分析，先要找到 倒数第 3 个节点的前一节点，即值为 2 的节点；
增加虚拟头节点
值为 2 的节点是 倒数第 4 个节点（后往前数），增加两指针 fast/slow，分别指向最后一个元素（NULL）和上图中 target 的位置；
此时 fast 跟 slow 之间的间距是固定（n = 3）的，找到 target(slow)后，只需要删除其下一节点即可，但 slow 指向的节点前面有多少个节点该如何确定呢？
由于当前已知 fast 和 slow 指向节点之间的长度是固定的，只需要将这两个指针向前挪，直到 slow 挪到虚拟头节点（值为 0）的位置，此时 fast 指向值为 4 的节点的位置，fast 只需要由虚拟头节点的位置 右移 n + 1 = 4 即可。如下图示：
当 fast 右移至值为 4 的节点时，指针 slow 和 fast 同时右移，直至 fast 移到 NULL，此时 slow 刚好到 target 位置，即指向 倒数第 n + 1 个节点，如下图示。
Show me the Code
c++
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode *slow = dummyHead, *fast = dummyHead;
for (int i = 0; i < n + 1; ++i) {
fast = fast->next;
}
while (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
ListNode* delNode = slow->next;
slow->next = delNode->next;
delete delNode;
ListNode* retNode = dummyHead->next;
delete dummyHead;
return retNode;
}
java
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode slow = dummyHead, fast = dummyHead;
for (int i = 0; i < n + 1; ++i) {
fast = fast.next;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
更多精彩，关注公众号【程序员小熊】
