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

题目

题目来源：力扣（LeetCode）

给你一个链表，删除链表的倒数第 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]

思路分析

快慢指针法

1、要删除链表中的某个节点，需要知道该节点的前一个节点。假如我删除的是头节点，但是头节点是没有前一个节点的，那怎么删除呢？此时我们可以定义一个虚拟头节点，让虚拟头节点的后续指针指向真正的头节点， 如下图：
2、题目中要删除的是链表中倒数的第二个节点，要删除倒数第二个节点，我们就要找到它的前一个节点，在这里删除的节点是 4，那它的前一个节点是3，我们定义一个慢指针 slow指向要删除节点的前一个节点，如下图：
3、那么如何确定慢指针 slow 的位置呢？我们还需要一个快指针。定义一个快指针 fast ，当快指针 fast 指向null 时，它与慢指针 slow 之间相差两个节点，刚好 n=2
4、那么又如何确定指针 fast 的位置呢？在链表中，通常我们只知道链表的头节点，要找到待删除的节点，就需要从头节点开始遍历链表。因此，我们将慢指针 slow 和快指针 fast 在初始时都指向虚拟头节点：
5、当 fast 指针指向 null的时候，slow指针指向待删除节点的前一个节点，它们之间相差着 n 个节点，也就是相差着 n+1 步，因此我们先让快指针fast向前走 n + 1 步。题意中 n = 2，所以 快指针 fast 先向前移动 3 步：
6、然后，让慢指针slow 和快指针fast 同时向前移动，每次移动一步：
7、直到快指针fast指向 null ，此时，慢指针所指向节点的下一个节点就是要删除的节点：
8、接下来要做的事情，就是将慢指针slow所指节点的后继指针指向待删除节点的下一个节点，然后待删除节点的后继指针指向null，即可将倒数第二个节点删除：

var removeNthFromEnd = function(head, n) {
    if (head == null) return null;
    // 创建一个虚拟头节点
    const hair = new ListNode(-1, head);
    // 慢指针初始时指向虚拟头节点
    let slow = hair;
    // 快指针初始时指向虚拟头节点
    let fast = hair;
    // 快指针向前移动 n+1 步
    for (let i = 0; i <= n; i++) {
        fast = fast.next;
    }
    // 快慢指针同时向前移动一步，直到快指针指向 null
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    // 当快指针指向 null，此时慢指针所指节点的下一个节点就是待删除的节点
    const delNode = slow.next;
    // 将慢指针所指节点的后继指针指向待删除节点的下一个节点
    slow.next = delNode.next;
    // 将待删除节点的后继指针指向 null，这样就可以将待删除节点删除了
    delNode.next = null;
    return hair.next;
};

借助 栈

我们也可以借助栈来删除链表中的节点。在遍历链表的同时，将所有的节点依次放入栈中。根据栈 「先进后出」的原则，我们弹出栈的第 n 个节点就是要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。此时我们只需要将前驱节点的后继指针指向待删除节点的后一个节点，即可将待删除节点删除。

var removeNthFromEnd = function(head, n) {
    if (head == null) return null;
    // 链表头节点
    const dummy = new ListNode(0, head);
    // 在这里使用数组模拟栈
    const stack = new Array();
    // 定义 curr 指针指向头节点
    let curr = dummy;
    // 遍历链表的同时将所有节点依次放入栈中
    while (curr != null) {
        stack.push(curr);
        curr = curr.next;
    }
    // 根据栈 「先进后出」的原则，弹出栈的第 n 个节点就是需要删除的节点
    for (let i = 0; i < n; i++) {
        stack.pop();
    }
    // 此时栈顶的节点就是待删除节点的前驱节点
    const prev = stack[stack.length - 1];
    // 将待删除节点的后继指针指向待删除节点的后一个节点，即可将待删除节点删除
    prev.next = prev.next.next;
    return dummy.next
};

其中算法的时间复杂度为 O(L)，L 是链表的长度，
空间复杂度为 O(L)，L 是链表的长度，主要为栈的开销。