算法（附思维导图+全部解法）19删除链表的倒数第 N 个结点

零标题：算法（leetode，附思维导图 + 全部解法）300题之（19）删除链表的倒数第 N 个结点

导读：

作者简介

1 作者简历

作者简历
2019年的微信小程序应用开发赛-全国三等奖

2 作者标签

1）“伪全栈工程师，主攻前端，偶尔写点后端”。

2）2019年的微信小程序应用开发赛 - 全国三等奖；
2019CODA比赛 - 前 17/211 强 且 荣获“优秀团队”称号 等。

3）“半自媒体人”，在校期间、个人公众号（IT三少。新自媒体（公众号）号：码农三少）在半年内实现了0到5.8K+的粉丝增长等。

一题目描述

题目描述

二解法总览（思维导图）

思维导图

三全部解法

1 方案1

1)代码：

// 方案1 “化归思想” —— “不熟悉的 --> 熟悉的”。
// 技巧：若 我们并不知道从 A-->C 的最佳路线、但知道 B-->C 的路线，
// 则 原先的 A-->C 问题就变成了 A-->B 问题。
var removeNthFromEnd = function(head, n) {
    // 1）初始化存储链表的数组。
    let tempArr = [];

    // 2）遍历链表，将 节点的值val 不断存入 tempArr 。
    while (head) {
        tempArr.push(head.val);
        head = head.next;
    }

    const l = tempArr.length;
    // 3）删除数组 tempArr 倒数第N个值 。
    tempArr.splice(l - n, 1);

    // 4）遍历删除单个特定元素后的数组 tempArr ，并将相应的值不断 填充到新的链表 。
    let index = 0,
        tempHead = resHead = null;
    // 边界：因为 l 是删除前的长度，故此处遍历条件是 index < l - 1 。
    while (index < l - 1) {
        // 4.1）若 下标为0 ，
        // 则 需要同时初始化 resHead（头结点，程序的返回值） 和 tempHead（临时节点，用于遍历、往后拉） 。
        if (index === 0) {
            resHead = tempHead = new ListNode(tempArr[index]);
        }
        // 4.2）若 下标为0 ，
        // 则 仅需处理 tempHead 即可。
        else {
            tempHead.next = new ListNode(tempArr[index]);
            tempHead = tempHead.next;
        }
        index++;
    }

    // 5）返回结果 resHead 。
    return resHead;
};

2 方案2

1)代码：

// 方案2 “2次遍历”。
// 技巧：第一次遍历 —— 知道该链表的节点个数（即长度 l ）。
// 第二次遍历 —— 通过节点的“重新赋值操作”，达到 “删除链表的倒数第N个结点” 的目的。
var removeNthFromEnd = function(head, n) {
    // 1）第一次遍历 —— 知道该链表的节点个数（即长度 l ）。
    let l = 0,
        // 注：头结点在遍历前需做 “备份” ！
        tempHead = resHead = head;

    while (tempHead) {
        tempHead = tempHead.next;
        l++;
    }

    // 2）第二次遍历 —— 通过节点的“重新赋值操作”，达到 “删除链表的倒数第N个结点” 的目的。

    // 又重新遍历，故需重置 tempHead 为 resHead 。
    tempHead = resHead;
    // 注：count 别写成了 l - n ！
    let count = l - n - 1;

    // 边界：删除头结点，直接返回 resHead.next 即可 。
    // case：head = [1], n = 1 。
    if (count === -1) {
        return resHead.next;
    }

    // 2.1）通过 count 计数器不断将 tempHead 往后拉。
    for (let i = 0; i < count; i++) {
        tempHead = tempHead.next;
    }

    // 2.2）重新赋值，将 此时tempHead 的下一个节点 删除 。
    tempHead.next = tempHead.next.next;

    // 3）返回结果 resHead 。
    return resHead;
}

3 方案3

1)代码：

// 方案3 “1次遍历”。
// 技巧：数组存节点的引用、地址。
// 第一次遍历，依次将 节点 存入 数组tempArr & 同时得到链表的长度 l 。
// 核心：1）const count = l - n - 1;    2）tempArr[count].next = tempArr[count].next.next;
var removeNthFromEnd = function(head, n) {
    // 1）初始化状态
    let resHead = tempHead = head,
        tempArr = [],
        l = 0;

    // 2）第一次遍历，依次将 节点 存入 数组tempArr & 同时得到链表的长度 l 。
    while (tempHead) {
        tempArr.push(tempHead);
        tempHead = tempHead.next;
        l++;
    }

    // 3）确定要删除节点的位置 —— count 。
    const count = l - n - 1;

    // 3.1）边界：若 删除的 是头结点 ，
    // 则 直接返回 resHead.next 即可 。
    // case：head = [1], n = 1 。
    if (count === -1) {
        return resHead.next;
    }

    // 3.2）边界：若 删除的 不是头结点 ，
    // 则 将 tempArr[count].next 节点跳过，
    // 即 下面一行代码（核心！） 。
    tempArr[count].next = tempArr[count].next.next;

    // 4）返回结果 resHead 。
    return resHead;
}

4 方案4

1)代码：

// 方案4 “双指针，即 快慢指针”。
// 注：这里作者也有点看不懂程序了，参考：
// 1）https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
var removeNthFromEnd = function(head, n) {
    // 1）状态初始化
    let resHead = new ListNode(0, head),
        slow = fast = resHead;

    // 2）处理
    while (n) {
        fast = fast.next;
        n--;
    }

    if (!fast) {
        return fast.next;
    }

    while (fast.next) {
        fast = fast.next;
        slow = slow.next;
    }

    // 3）删除相应的节点
    slow.next = slow.next.next;

    // 4）返回结果（因为一开始是 resHead = new ListNode(0, head) ）
    return resHead.next;
}