Description

算法步骤

解法一 双指针

假设一把尺子，l代表尺子的左边，r代表尺子的右边。那么假如从l到r有m个节点，我们把这把尺子的右边对齐整条链表的右边。那么从左往右数是1到m个节点，则从右往左数肯定也是1到m个节点。因此，如果你要删除倒数第m个节点的话，那么l就是倒数第m个节点。

但为了删除倒数第m个节点，我们就需要找到倒数第m+1个节点。方式也是一样的，我们先让尺子变的更长让l到r有m+1个节点，然后把尺子放到链表的右边，那么l就是倒数第m+1个节点。通过这个节点我们就能够删除倒数第m个节点。方式是l.next = l.next.next。

不过，如果链表长度为1，那么l和r都是同一个节点，那么l.next = l.next.next就会报错。因此，我们需要一个虚拟头节点来解决这个问题。

解法二 遍历两次链表

遍历一次指针计算链表总长度，通过倒数第n个，计算出它是正数第几个节点B，然后遍历B前的节点A。通过A节点删除B节点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 * val: number
 * next: ListNode | null
 * constructor(val?: number, next?: ListNode | null) {
 * this.val = (val===undefined ? 0 : val)
 * this.next = (next===undefined ? null : next)
 * }
 * }
 */

// 双指针解法
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(-1, null);
  dummy.next = head;

  let l = dummy;
  let r = dummy;

  while (n > 0) {
    r = r.next!;
    n--;
  }

  while (r.next) {
    l = l.next!;
    r = r.next!;
  }

  l.next = l.next!.next;

  return dummy.next;
};

// 遍历两次链表解法
function removeNthFromEnd1(head: ListNode | null, n: number): ListNode | null {
  // 1，2，3，4，5，倒数第1，就是正数第5。倒数第2，就是正数第4，倒数第3，就是正数第3。
  // 5 1 5 ｜ 5 2 4 ｜ 5 3 3 ｜ 5 4 2 ｜ 5 5 1
  // 因此s个节点，倒数第i，就是正数第(s+1) - i;

  const dummy = new ListNode(-1, null);

  dummy.next = head;

  let total = 0;

  while (head) {
    total++;
    head = head.next;
  }

  let curLoc = 0;
  let curNode = dummy;
  let targetLoc = total + 1 - n;

  while (curLoc < targetLoc - 1) {
    curLoc++;
    curNode = curNode.next!;
  }

  const toDelete = curNode.next;

  curNode.next = toDelete!.next;
  toDelete!.next = null;

  return dummy.next;
};
Copy