哨兵节点：思想简单，效果很棒的编程算法("哨兵节点：简洁高效，编程算法中的隐藏神器")

原创

ithorizon 7个月前 (10-20) 阅读数 15 #后端开发

哨兵节点：简洁高效，编程算法中的隐藏神器

一、引言

在编程世界中，算法是解决问题的基础。有些算法因其纷乱性和高效性而广为人知，如敏捷排序、二分查找等。然而，还有一些简洁高效但鲜为人知的算法，它们在特定场景下发挥着巨大的作用。今天，我们要介绍的就是这样一个算法：哨兵节点。

二、什么是哨兵节点？

哨兵节点，又称“哨兵模式”，是一种在数据结构中添加特殊节点的方法，用于简化算法的实现和优化程序的性能。哨兵节点通常是一个具有特殊值的节点，它在数据结构中起到了“守卫”的作用，令算法在处理边界情况时更为简洁和高效。

三、哨兵节点的应用场景

哨兵节点广泛应用于链表、树、图等数据结构中。以下是一些典型的应用场景：

1. 链表中的哨兵节点

在单链表中，哨兵节点通常被用作链表的头节点。这样，在进行链表操作时，我们不需要额外判断头节点是否为空，从而简化了算法的实现。


        // 定义链表节点
        class ListNode {
            int val;
            ListNode next;
            ListNode(int x) { val = x; }
        }
        // 带哨兵节点的链表操作
        ListNode sentinel = new ListNode(0); // 创建哨兵节点
        sentinel.next = head; // 将哨兵节点指向链表头节点
        // 遍历链表
        ListNode current = sentinel;
        while (current.next != null) {
            // 执行操作
            current = current.next;
        }

2. 树中的哨兵节点

在二叉搜索树中，哨兵节点可以用于描述空子树。当进行插入、删除等操作时，哨兵节点可以避免对空子树的额外判断，减成本时间算法的快速。


        // 定义二叉搜索树节点
        class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }
        // 带哨兵节点的二叉搜索树
        TreeNode sentinel = new TreeNode(Integer.MIN_VALUE); // 创建哨兵节点
        sentinel.left = root; // 将哨兵节点指向根节点
        // 插入节点
        public TreeNode insert(TreeNode root, int val) {
            TreeNode current = sentinel;
            TreeNode parent = null;
            while (current != null) {
                parent = current;
                if (val < current.val) {
                    current = current.left;
                } else if (val > current.val) {
                    current = current.right;
                } else {
                    return root; // 已经存在该值
                }
            }
            TreeNode newNode = new TreeNode(val);
            if (val < parent.val) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
            return root;
        }

3. 图中的哨兵节点

在图的邻接表描述中，哨兵节点可以用于描述不存在的边。这样，在遍历图时，我们可以避免对不存在的边的额外判断，减成本时间算法的快速。


        // 定义图节点
        class GraphNode {
            int val;
            List neighbors;
            GraphNode(int x) { val = x; neighbors = new ArrayList<>(); }
        }
        // 带哨兵节点的图
        GraphNode sentinel = new GraphNode(-1); // 创建哨兵节点
        List graph = new ArrayList<>();
        graph.add(sentinel); // 将哨兵节点添加到图中
        // 遍历图
        for (GraphNode node : graph) {
            if (node == sentinel) continue; // 跳过哨兵节点
            // 执行操作
        }