4.2 哨兵节点

哨兵节点是为了简化处理链表边界条件而引入的附加链表节点。哨兵节点通常位于链表的头部，它的值没有任何意义。在一个有哨兵节点的链表中，从第2个节点开始才真正保存有意义的信息。

❖ 用哨兵节点简化链表插入操作

链表的一个基本操作是在链表的尾部添加一个节点。由于通常只有一个指向单向链表头节点的指针，因此需要遍历链表中的节点直至到达链表的尾部，然后在尾部添加一个节点。可以用如下所示的Java代码实现这个过程：

上述代码中有一个值得注意的细节：当输入的链表头节点为null时，输入的链表为空。此时新添加的节点成为链表中唯一的节点，也就是链表的头节点。在这种情况下，我们改变了输入链表的头节点，因此在上述代码中有一条用来处理这种情况的if语句。

还有另外一种方法可以在链表的尾部添加一个节点。首先创建一个哨兵节点，并把该节点当作链表的头节点，然后把原始的链表添加在哨兵节点的后面。当完成添加操作之后，再返回链表真正的头节点，也就是哨兵节点的下一个节点。这种思路的代码如下所示：

由于将新创建的一个哨兵节点当作链表的头节点，链表无论如何也不会为空，因此不需要使用if语句来单独处理输入头节点head为null的情形。哨兵节点简化了代码的逻辑。

❖ 用哨兵节点简化链表删除操作

下面讨论如何从链表中删除第1个值为指定值的节点。通常为了删除一个节点，应该找到被删除节点的前一个节点，然后把该节点的next指针指向它下一个节点的下一个节点，这样下一个节点没有被其他节点引用，也就相当于被删除了。由于需要逐一遍历链表中的节点以便找到第1个指定值的节点，因此不难写出如下所示的代码：

在上述代码中有两条if语句，分别用于处理两个特殊情况：输入的链表为空；被删除的节点是原始链表的头节点。

如果在链表的最前面添加一个哨兵节点作为头节点，那么链表就不为空，并且链表的头节点无论如何都不会被删除。因此，也可以用哨兵节点来简化从链表中删除节点的代码逻辑：

输入的链表为空，或者操作可能会产生新的头节点，这些都是应聘者在面试时特别容易忽视的测试用例。如果合理应用哨兵节点，就不再需要单独处理这些特殊的输入，从而杜绝由于忘记处理这些特殊输入而出现Bug的可能性。

解题小经验

使用哨兵节点可以简化创建或删除链表头节点操作的代码。