哨兵节点

哨兵节点解决什么问题？

• 问题: 被操作的位置在第一个结点时, 需要单独判断并修改外部持有的 head 引用;
• 哨兵: 在 head 前挂一个值无意义的 dummy, 所有增删都发生在 dummy 之后;
• 返回: 结果链表一律从 dummy.next 取;

const dummy = new ListNode(-1, head);
// ... 在 dummy 之后增删
return dummy.next;

删除排序链表中的重复元素时都要哨兵吗？

题	删除规则	需要哨兵	原因
83	重复元素保留一个	否	head 一定被保留
82	重复出现的元素全部删除	是	head 可能整段被删掉

• 83: current.val === current.next.val 时 current.next = current.next.next, 否则 current = current.next;
• 82: 用 pre 指向已确认保留的尾结点, 用 cur 扫描相同值的一段, 一次性 pre.next = cur.next;

// 83
const deleteDuplicates = (head) => {
  let cur = head;
  while (cur && cur.next) {
    if (cur.val === cur.next.val) cur.next = cur.next.next;
    else cur = cur.next;
  }
  return head;
};

// 82
const deleteDuplicatesAll = (head) => {
  const dummy = new ListNode(-1, head);
  let pre = dummy;
  let cur = head;
  while (cur && cur.next) {
    if (cur.val !== cur.next.val) {
      pre = cur;
      cur = cur.next;
    } else {
      while (cur.next && cur.val === cur.next.val) cur = cur.next;
      pre.next = cur.next;
      cur = cur.next;
    }
  }
  return dummy.next;
};

还有哪些场景用哨兵统一边界？

• 删除倒数第 N 个结点: 哨兵让"删第一个"与"删中间"共用一套指针, 见 链表中双指针;
• 分隔链表: 两个哨兵分别接 < x 与 >= x 的结点, 最后拼接, 见 链表分组;
• 两数相加: 哨兵作为结果链表的锚点, 见 链表数值运算;
• 反转链表: 迭代反转的返回值就是 pre, 前置哨兵不是必需;