為什麼需要哨兵節點 (Sentinel Node)?

利用哨兵節點可以讓 edge case 處理起來更容易， 在處理 Linked list 相關問題時，可以問自己下列問題，確認是否都有好好處理 edge case 了:

• 如果 linked list 為空，程式碼是否能正常工作？
• 如果 linked list 只包含一個節點，程式碼是否能正常工作？
• 如果 linked list 只包含兩個節點，程式碼是否能正常工作？
• 在頭節點與尾節點，程式碼是否能正常工作？

針對 edge case 通常需要另外寫判斷式，有 sentinel node 的協助，可以使用較 general 的寫法來解決問題，降低實作難度。

利用哨兵簡化實作難度

以下舉個例子，如果以單向 linked list 來看，一般插入新節點會像下面這樣寫：

new_node->next = p->next;
p->next = new_node;

但如果新節點要做為第一個節點時，必須做增加額外的判斷式 :

if (head == NULL) {
    head = new_node;
}

加上哨兵節點後，就不必再做額外的判斷式，哨兵節點就是一個單純的空節點，他的 value 是什麼不重要，只是需要他來讓程式碼可以寫得更簡潔。

以下舉兩題應用哨兵節點 (Sentinel Node) 的題目 :

LC #019 Remove Nth Node From End of List

以下為沒有 sentinel node 的做法，利用 two pointer 的技巧，先讓 fast pointer 往前走 n 步，接著兩個 pointer 都一起前進，直到 fast pointer 走到最後一個節點時， slow pointer 的 next 節點就是需要被移除的：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* slow = head, *fast = head;

        for (int i=0; i<n; i++)
            fast = fast->next;

        while (fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

這在大部分 case 下都是可行的，但是當 input 為 [1, 2], n = 2 ，剛好要移除的就是頭節點時，上述作法就會失敗。需要特別處理當刪除節點為頭節點的 case ，但如果使用 sentinel node ，整個演算法就可以設計得更 general 。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
                // front pointer points to the head pointer
        struct ListNode front(0, head);
        ListNode *walker = &front, *runner = &front;

        for (int i=0; i<n+1; i++)
        {
            runner = runner->next;
        }

        while (runner != nullptr)
        {
            walker = walker->next;
            runner = runner->next;
        }
        walker->next = walker->next->next;
        return front.next;
    }
};

LC #086 Partition List

為了保持原本節點之間的順序，透過維護兩個 Linked list ，一條用來存放比 value x 小的，另一條H存放 ≥ value x 的 node 。

以下是不使用哨兵節點的做法，你會遇到好多的 edge cases 需要處理 :

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *before = nullptr;
        ListNode *after = nullptr;
        ListNode *after_head = nullptr;
        ListNode *before_head = nullptr;

        while (head)
        {
            if (head->val < x)
            {
                if (before == nullptr) {
                    before = head;
                    before_head = head;
                }
                else {   
                    before->next = head;
                    before = before->next;
                }
            }
            else
            {
                if (after == nullptr) {
                    after = head;
                    after_head = head;
                }
                else {
                    after->next = head;
                    after = after->next;
                }
            }
            head = head->next;
        }
        if (after != nullptr)
            after->next = nullptr;
        if (before_head != nullptr && after_head != nullptr)
            before->next = after_head;
        if (before_head == nullptr)
            return after_head;
        return before_head;
    }
};

使用哨兵節點後，程式碼變得相當簡潔:

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode node1(0);
        ListNode node2(0);
        ListNode *before = &node1;
        ListNode *after = &node2;

        while (head)
        {
            if (head->val < x)
            {
                before->next = head;
                before = before->next;
            }
            else
            {
                after->next = head;
                after = after->next;
            }
            head = head->next;
        }
        after->next = nullptr;
        before->next = node2.next;
        return node1.next;

    }
};