哨兵位（Sentinel Node）的作用

哨兵位是鏈表中的一個特殊節點，它并不保存有效數據，只是作為標識存在。使用哨兵位有以下幾個好處：

• 統一處理：哨兵位使得鏈表的插入和刪除操作可以統一處理，無需區分鏈表為空、頭節點或尾節點等特殊情況。
• 簡化代碼：避免了空鏈表的處理、頭節點的特殊處理等復雜情況，使得代碼更加簡潔。

下面我們來實戰演練。

實戰演練

合并兩個有序鏈表 - 力扣（LeetCode）

這道題的解法很多，這里我們使用最優的方法——雙指針遍歷

思路講解

通過兩個指針同時遍歷兩個鏈表，逐個比較鏈表中的節點，將較小的節點接到合并后的鏈表上，直到一個鏈表遍歷完成，再將另一個鏈表中剩余的部分直接接到結果鏈表后。

詳細步驟

1. 處理特殊情況（邊界條件）

if(list1 == NULL)return list2;
if(list2 == NULL)return list1;

如果其中一個鏈表為空，直接返回另一個鏈表。這樣可以避免后續操作中對空鏈表的額外處理。

2. 創建哨兵節點

struct ListNode* tail = NULL, *guard = NULL;
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next = NULL;

• 創建一個哨兵節點guard，該節點不會保存實際的數據。它的作用是簡化鏈表的操作，特別是頭節點的處理。因為如果直接操作鏈表頭節點，可能需要單獨判斷頭節點是否為空或其他邊界情況，使用哨兵節點后，我們就可以統一處理所有節點的插入。
• tail指針用于指向合并鏈表的尾部。通過這個指針，我們可以方便地將新的節點插入到合并后的鏈表中。

3. 初始化兩個指針，遍歷兩個鏈表

struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;

• cur1和cur2分別指向兩個輸入鏈表list1和list2的頭節點。我們將使用這兩個指針遍歷兩個鏈表，進行比較并合并。

4. 合并兩個鏈表

while(cur1 && cur2) {if(cur1->val < cur2->val) {tail->next = cur1;cur1 = cur1->next;tail = tail->next;} else {tail->next = cur2;cur2 = cur2->next;tail = tail->next;}
}

• 這里使用一個while循環，循環條件是cur1和cur2都不為空。也就是說，只有當兩個鏈表中都有節點時，才會進入循環。
• 在循環內部，比較cur1和cur2所指向節點的值，選擇較小的節點加入到合并后的鏈表中：
  • 如果cur1的值小于cur2的值，就將cur1節點連接到tail的next上，并將cur1向后移動一個節點。
  • 否則，將cur2節點連接到tail的next上，并將cur2向后移動一個節點。
• 每次將新的節點連接到tail之后，更新tail指針，指向合并鏈表的最后一個節點。

5. 處理剩余節點

if(cur1)tail->next = cur1;
if(cur2)tail->next = cur2;

• 在上面的while循環結束后，可能會有一個鏈表的節點已經全部被處理完，另一個鏈表中還有節點沒有被合并。
• 如果cur1指向的鏈表中還有節點未處理（即cur1不為空），將剩余的cur1節點直接接到合并鏈表的尾部。
• 同理，如果cur2指向的鏈表中還有節點未處理（即cur2不為空），將剩余的cur2節點直接接到合并鏈表的尾部。

6. 返回合并后的鏈表

struct ListNode* head = guard->next;
free(guard);
return head;

• 合并后的鏈表的頭節點是guard->next，因為guard本身是一個哨兵節點，不保存實際的數據。返回guard->next就是合并后的鏈表的頭節點。
• 最后，釋放掉guard節點占用的內存，因為guard節點已經不再需要。

完整代碼

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {// 如果list1為空，返回list2if(list1 == NULL)return list2;// 如果list2為空，返回list1if(list2 == NULL)return list1;struct ListNode* tail = NULL, *guard = NULL;struct ListNode* cur1 = list1;struct ListNode* cur2 = list2;// 創建一個哨兵節點guard，方便操作鏈表頭guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));tail->next = NULL;// 合并兩個鏈表while(cur1 && cur2) {// 判斷當前cur1的值與cur2的值，選擇較小的節點if(cur1->val < cur2->val) {tail->next = cur1;cur1 = cur1->next;  // 移動cur1指針tail = tail->next;   // 更新tail指針} else {tail->next = cur2;cur2 = cur2->next;  // 移動cur2指針tail = tail->next;   // 更新tail指針}}// 如果cur1還有剩余，連接到tailif(cur1)tail->next = cur1;// 如果cur2還有剩余，連接到tailif(cur2)tail->next = cur2;// 頭指針是guard的下一個節點struct ListNode* head = guard->next;// 釋放哨兵節點free(guard);return head;
}

結語

如果這道題不用哨兵位，你將會被一個錯誤搞的焦頭爛額——對空指針解引用，不相信的話你可以去試試，你一定會影響深刻的。

通過這道題，是不是覺得哨兵位真的很香？非常省事，特別是這種多鏈表的聯合問題，我們一定要留個心眼。