4.2 哨兵節點

哨兵節點是為了簡化處理鏈表邊界條件而引入的附加鏈表節點。哨兵節點通常位于鏈表的頭部，它的值沒有任何意義。在一個有哨兵節點的鏈表中，從第2個節點開始才真正保存有意義的信息。

? 用哨兵節點簡化鏈表插入操作

鏈表的一個基本操作是在鏈表的尾部添加一個節點。由于通常只有一個指向單向鏈表頭節點的指針，因此需要遍歷鏈表中的節點直至到達鏈表的尾部，然后在尾部添加一個節點。可以用如下所示的Java代碼實現這個過程：

上述代碼中有一個值得注意的細節：當輸入的鏈表頭節點為null時，輸入的鏈表為空。此時新添加的節點成為鏈表中唯一的節點，也就是鏈表的頭節點。在這種情況下，我們改變了輸入鏈表的頭節點，因此在上述代碼中有一條用來處理這種情況的if語句。

還有另外一種方法可以在鏈表的尾部添加一個節點。首先創建一個哨兵節點，并把該節點當作鏈表的頭節點，然后把原始的鏈表添加在哨兵節點的后面。當完成添加操作之后，再返回鏈表真正的頭節點，也就是哨兵節點的下一個節點。這種思路的代碼如下所示：

由于將新創建的一個哨兵節點當作鏈表的頭節點，鏈表無論如何也不會為空，因此不需要使用if語句來單獨處理輸入頭節點head為null的情形。哨兵節點簡化了代碼的邏輯。

? 用哨兵節點簡化鏈表刪除操作

下面討論如何從鏈表中刪除第1個值為指定值的節點。通常為了刪除一個節點，應該找到被刪除節點的前一個節點，然后把該節點的next指針指向它下一個節點的下一個節點，這樣下一個節點沒有被其他節點引用，也就相當于被刪除了。由于需要逐一遍歷鏈表中的節點以便找到第1個指定值的節點，因此不難寫出如下所示的代碼：

在上述代碼中有兩條if語句，分別用于處理兩個特殊情況：輸入的鏈表為空；被刪除的節點是原始鏈表的頭節點。

如果在鏈表的最前面添加一個哨兵節點作為頭節點，那么鏈表就不為空，并且鏈表的頭節點無論如何都不會被刪除。因此，也可以用哨兵節點來簡化從鏈表中刪除節點的代碼邏輯：

輸入的鏈表為空，或者操作可能會產生新的頭節點，這些都是應聘者在面試時特別容易忽視的測試用例。如果合理應用哨兵節點，就不再需要單獨處理這些特殊的輸入，從而杜絕由于忘記處理這些特殊輸入而出現Bug的可能性。

解題小經驗

使用哨兵節點可以簡化創建或刪除鏈表頭節點操作的代碼。