第十九题 - 删除链表的倒数第N个节点

[laizimo]

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。

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

算法

双指针法

答案

/**
 * 双指针法
 */
var removeNthFromEnd = function(head, n) {
    // #1 设置指针
    let res = curr = end = head;
    let prev = null;
    // #2 设置计数器
    let count = 1;
    // #3 遍历链表
    while (end) {
        // #4 如果计数器大于n，curr指针开始移动
        if (count > n) {
            prev = curr;
            curr = curr.next;
        }
        // #5 结束指针移动，计数器加一
        end = end.next;
        count++;
    }
    // #6 如果prev不存在，说明删除第一个
    if (!prev) return res.next;
    // #7 删除当前节点
    prev.next = curr.next;
    return res;
};