数据结构与算法 / 系统课时

用哨兵节点简化链表边界

用哨兵节点简化链表边界

单链表题最容易出错的地方往往不是指针移动,而是首节点没有前驱:删除头节点、在头部插入或构造新链表时,都容易被迫增加特殊分支。哨兵节点通过在真实头节点之前放置一个固定的虚拟节点,让首节点和中间节点都能使用同一套指针操作。

学习目标

  • 理解哨兵节点如何为真实头节点补出稳定的前驱
  • 能使用虚拟头节点统一链表删除、插入和结果链表构造逻辑
  • 能正确区分工作指针 dummy 与最终应返回的真实头节点 dummy.next

首节点为什么总要特判

在单链表中删除某个节点,通常需要让它的前驱执行 prev.next = prev.next.next。如果待删除的是中间节点,prev 天然存在;但如果待删除的是当前头节点,就没有真实前驱,只能单独修改 head。

哨兵节点的做法是在头部人为添加一个不会作为业务数据返回的节点,使原来的 head 变成 dummy.next。这样即使删除第一个真实节点,也仍然存在前驱 dummy,边界操作就可以复用普通节点的逻辑。

哨兵节点统一链表删除边界

用同一段循环删除任意位置

下面删除链表中所有值为 7 的节点。示例故意让目标值同时出现在头部、中间和尾部,用来验证哨兵节点是否真正覆盖了边界。

java
public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    static ListNode removeElements(ListNode head, int target) {
        // dummy 永远保留,因此真实头节点始终拥有一个可用前驱。
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        while (prev.next != null) {
            if (prev.next.val == target) {
                // 删除后不移动 prev,以便继续检查新的 prev.next。
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return dummy.next;
    }

    static ListNode build(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int value : values) {
            tail.next = new ListNode(value);
            tail = tail.next;
        }
        return dummy.next;
    }

    static void printList(ListNode head) {
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val);
            if (p.next != null) {
                System.out.print(" -> ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode head = build(7, 1, 7, 2, 7);
        printList(removeElements(head, 7));
    }
}

预期输出:

text
1 -> 2

循环始终检查 prev.next,而不是直接把当前节点作为待删除对象。删除成功时 prev 不移动,因为新的 prev.next 可能仍然等于目标值;只有保留当前节点时,才把 prev 向后推进。这也能正确处理多个目标节点连续出现的情况。

哨兵节点还能统一哪些操作

插入节点时,如果题目要求“在某节点之前插入”,真实头节点同样缺少前驱。增加 dummy 后,可以从它开始寻找插入位置,再通过修改 prev.next 完成操作,不需要为头部插入单写分支。

合并两个有序链表时,哨兵节点还有另一种价值:它提供一个固定的结果链表起点。令 tail 从 dummy 开始,每次把较小节点接到 tail.next,最后直接返回 dummy.next。这样不用在第一次追加节点时判断“结果链表是否还是空的”。

使用哨兵时容易犯的错

哨兵节点减少的是边界分支,并不会自动保证指针移动正确。删除节点后若无条件执行 prev = prev.next,就可能跳过连续待删除节点;构造结果链表时若最后返回 dummy,则会把虚拟节点错误地暴露给调用者。

判断是否值得使用哨兵,可以看操作是否反复碰到“头节点没有前驱”这一问题。只要删除、头部插入、链表合并或分区过程中需要统一首节点与中间节点的处理,先建立 dummy -> head 往往能让后续循环只维护一种不变量,代码也更容易验证。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用哨兵节点简化链表边界

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通