删除链表的倒数第 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]

思路&js代码

1、左右指针

var removeNthFromEnd = function(head, n) {
    // 由于可能会删除链表头部，用哨兵节点简化代码
    const dummy = new ListNode(0, head);
    let left = dummy;
    let right = dummy;
    while (n--) {
        right = right.next; // 右指针先向右走 n 步
    }
    while (right.next) {
        left = left.next;
        right = right.next; // 左右指针一起走
    }
    left.next = left.next.next; // 左指针的下一个节点就是倒数第 n 个节点
    return dummy.next;
};