【LeetCode】19. 删除链表的倒数第 N 个结点（中等）——代码随想录算法训练营Day04

题目链接：19. 删除链表的倒数第 N 个结点

题目描述

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

提示：

链表中结点的数目为?sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

文章讲解：代码随想录

视频讲解：链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点_哔哩哔哩_bilibili

题解1：暴力法

思路：先遍历一遍链表得出链表总长度，再通过计算删除链表倒数第 n 个节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    // 第1次遍历，得出链表元素的个数
    let size = 0;
    let cur = head;
    while (cur) {
        size++;
        cur = cur.next;
    }


    // 链表中元素的位置为0,1,2,...,size -1
    // 倒数第1个元素位置为 size -1，倒数第2个为 size - 2，倒数第 n 个为 size - n
    // 要取 size - n - 1 位置的元素，需要取头指针向后移动 size - n - 1 位
    const vHead = new ListNode(0, head); // 虚拟头节点
    cur = vHead;
    for (let i = 0; i < size - n; i++) {
        cur = cur.next;
    }
    // 删除 cur 位置的下一个元素
    cur.next = cur.next ? cur.next.next : null;
    return vHead.next;
};

分析：遍历了2次链表，时间复杂度为 O(n)，空间复杂度为 O(1)。

题解2：快慢指针

思路：可以使用快慢指针的思想来解这道题。初始化时让快指针和慢指针都指向头节点，先让快指针前进 n 步，再让快指针和慢指针同时前进，当快指针到达链表结束时，慢指针就指向了倒数第 n 个节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    const vHead = new ListNode(0, head); // 虚拟头节点
    let slow = fast = vHead; // 初始化快慢指针
    // 快指针先前进 n + 1 步
    for (let i = 0; i < n + 1; i++) {
        fast = fast.next;
    }
    // 快慢指针同步移动，当快指针移动到链表末尾时，慢指针指向倒数第 n 个元素的上一个元素
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }
    // 删除慢指针位置的下一个元素
    slow.next = slow.next.next;
    return vHead.next;
};

分析：使用了快慢指针法，只对链表进行了一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

收获

学会了一种非常巧妙的快慢指针思路，虽然单链表无法像数组一样可以通过下标索引直接找到对应元素，但利用快慢指针之间的差值寻找倒数元素这种方法还是很精妙的。