删除链表的倒数第N个节点

[Cosen95]

leetcode: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

[Cosen95]

题目分析

分析题目，题干有两个关键点：

• 删除
• 倒数第N个节点

对应删除操作。我们一般是需要找到被删除节点的前驱节点。而删除操作一般会用到dummy 结点。

这道题目中提到了dummy 结点：它可以帮我们处理掉头结点为空的边界问题，帮助我们简化解题过程。

const dummy = new ListNode()
// 这里的 head 是链表原有的第一个结点
dummy.next = head

链表的删除没有什么难度（改变要被删除节点的前驱节点的next指向即可）。这道题的难点实际在于这个倒数第 N 个如何定位。

我们正常遍历时不太可能从后往前走，因此这个倒数第 N 个”完全可以转换为正数第 len - n + 1个。

定位这个节点，我们需要两次遍历：‘

• 第一次遍历得到链表的长度len
• 第二次遍历得到被删除节点（len-n+1）的前驱节点（len-n）

到这里，答案已经呼之欲出了。

不过，等等，还有更好的解决方法吗？

其实，我们可以用快慢指针来解决：

• 首先两个指针 slow 和 fast，全部指向链表的起始位——dummy 结点;
• 快指针先出发,走上 n 步，在第 n 个结点处停住;
• 然后，快慢指针一起前进，当快指针前进到最后一个结点处时，两个指针再一起停下来;
• 此时，慢指针所指的位置，就是倒数第 n 个结点的前一个结点;
• 我们基于这个结点来做删除就可以了。

编码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode();
    dummy.next = head;
    let fast = dummy,
        slow = dummy;
    while(n !== 0) {
        fast = fast.next;
        n--
    }
    while(fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
};