手帐 Blog

主题

复盘 · LC 19 删除链表的倒数第 N 个结点 ​

题目 ​

题意 ​

给定单链表头与正整数 n，删除倒数第 n 个结点，返回新头。

  • n 保证合法（1 ≤ n ≤ 链表长度）。
  • 可能删的是头结点（n === len）。

边界：单结点删唯一、两结点删头/删尾、长链删中间。

涉及算法 ​

标签一句话
两次遍历先数长度，再走到「待删前驱」断开
快慢指针 + 哨兵fast 先走 n 步，再同步；slow.next 即待删；dummy 统一删头

教程对照：12 · 链表基础 已给本题标准模板（哨兵 + 快慢）。

评价我的解法 ​

我的代码（摘自 19-删除链表的倒数第N个结点/index.js，不含本地测例）：

javascript
var removeNthFromEnd = function (head, n) {
  if (!head) {
    return null;
  }
  if (!head.next && n === 1) {
    return null;
  }
  let cur = head,
    next = null;
  let i = 0;
  let len = 0;
  while (cur) {
    if (cur.next) {
      next = cur.next;
    } else {
      next = null;
    }
    i++;
    cur = next;
  }
  len = i;
  i = 0;
  cur = head;
  next = null;
  while (cur) {
    if (cur.next) {
      next = cur.next;
    } else {
      next = null;
    }
    if (i == len - n - 1) {
      console.log(i, cur.val, len, n);
      if (next && next.next) {
        cur.next = next.next;
      } else {
        cur.next = null;
      }
      break;
    } else if (len === n && i === 1) {
      head = cur;
      break;
    }
    i++;
    cur = next;
  }
  return head;
};

能过题：先数 len，再定位前驱下标 len - n - 1 做跳过；删头走 len === n 的旁路。

  • 时间 O(n)（两遍），空间 O(1)——复杂度可接受。
  • 对在哪：长度法思路清晰；单结点删头单独 return；本地测了两结点删头。
  • 糙在哪：
    1. 删头用 i === 1 时 head = cur，本质是「多走一步再改头」，和中间删除不是同一套语义，难讲也易改崩。
    2. 解里留了 console.log，提交前应清掉。
    3. 每步用 if (cur.next) 赋 next，等价于 next = cur.next，噪音大。
    4. 没用哨兵 / 快慢——教程里本题本就是「快慢预热」，今天等于绕开了该练的肌肉。

正确性够用，但和「默写模板」还有一段距离。

最佳题解 ​

哨兵 + 快慢（一遍扫完，删头也统一）：

javascript
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  const dummy = new ListNode(0, head);
  let fast = dummy;
  let slow = dummy;
  for (let i = 0; i < n; i++) fast = fast.next;
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
};
  • 时间 O(n)，空间 O(1)。
  • 为何更优：fast 先拉开 n 的距离；fast 到尾时 slow 停在待删前驱；dummy 让「删头」与「删中」同一行 slow.next = slow.next.next。

口述口诀：哨兵开头，快针先走 n，齐步走到尾，慢针的 next 扔掉。

关联题目 ​

题为何相关
876. 链表的中间结点同款快慢距离差
203. 移除链表元素哨兵删结点模板
61. 旋转链表也常先数长度或快慢对齐

一句话带走 ​

删倒数第 n：先别数长度特判删头——dummy + 快针先走 n，慢针停前驱，一行跳过。