删除链表的倒数第 N 个结点 2022-02-26 周六

题目

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

示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

力扣官网解法

思路

• 判空，一般直接返回空；

• dummy节点：
  在head的前面增加一个dummy节点，辅助操作

• 快慢指针：
  快指针指向head；慢指针指向dummy；==== 一开始就错开一步

• 移动快指针n次

• 一起移动，直到快指针结束

• 删除慢指针的下一个节点

• 返回dummy.next

其他思路：先用一个指针遍历一遍求出链表的元素个数size
然后删除第size-n+1个元素就好了

JS代码

/**
 * 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) {
    // 判空
    if (head == null) {
        return null;
    }

    // 增加一个dummy节点
    let dummy = new ListNode();
    dummy.val = 0;
    dummy.next = head;

    // 快慢指针
    let quick = head;
    let slow = dummy;

    // 快指针先移动n次
    for (let i = 0; i < n; i++) {
        quick = quick.next;
    }

    // 两个一起走，直到快指针走完
    while(quick) {
        quick = quick.next;
        slow = slow.next;
    }

    // 删除目标就是slow的下一个
    slow.next = slow.next.next

    // 结果是dummy的下一个
    return dummy.next;
};

备注：

虽然C的性能高，但是表达起来JS最方便；
学算法才是主要的，所以用JS表达。