哨兵节点（Sentinel+Node）

📖 什么是哨兵节点？

【数据结构】关于链表中哨兵结点(sentinel)问题的深入剖析_链表的哨兵节点-CSDN博客

哨兵节点是一种用于简化链表操作的设计模式，通常是一个 不参与链表数据存储的特殊节点，其主要目的是 简化边界条件的处理，避免对链表头节点进行特殊处理。

哨兵节点通常会放在链表的开头（有时也可以放在末尾），但它的 值并不代表链表中的有效数据，而是充当一个“占位符”角色，使得链表操作更加统一、简洁。

🧠 哨兵节点的特点：

• 不包含有效数据：哨兵节点的值通常没有实际意义，它只是一个占位符。
• 简化操作：它的存在避免了链表为空或者包含一个元素时需要特殊判断的情况。
• 操作一致性：使用哨兵节点后，所有链表的操作都可以统一进行，而无需单独处理头节点或尾节点的特殊情况。

---

🔍 为什么需要哨兵节点？

在没有哨兵节点的情况下，链表头节点的处理通常需要特别关注。比如，插入和删除操作时，链表的头节点可能需要单独处理。例如：

• 插入时，如果链表为空，直接插入一个节点；
• 删除时，如果删除的是头节点，需要特殊处理头节点指向下一个节点。

哨兵节点的引入 避免了对空链表和非空链表的不同处理，使得在链表头部的插入、删除等操作都变得非常简洁。

---

🛠 哨兵节点的应用：

1. 简化插入操作

在没有哨兵节点时，插入操作需要考虑链表为空或非空的不同情况。而使用哨兵节点后，链表的插入可以不需要额外判断是否为空，只需要直接插入。

假设我们需要在链表的头部插入一个新的节点。

• 没有哨兵节点的情况下：

  if (head == nullptr) {
      head = newNode;
  } else {
      newNode->next = head;
      head = newNode;
  }

  如果链表为空，我们需要执行特殊的检查。

• 使用哨兵节点后：

  dummy->next = newNode;
  newNode->next = head;
  head = newNode;

  这里，我们不需要判断链表是否为空，插入操作更加简洁。

2. 简化删除操作

删除链表中的节点时，特别是删除头节点，往往需要特殊处理。在没有哨兵节点时，我们必须判断是否删除的是头节点，做一些额外的操作。

• 没有哨兵节点的删除：

  if (head == nullptr) {
      return nullptr;
  } else {
      ListNode* temp = head;
      head = head->next;
      delete temp;
  }

• 使用哨兵节点的删除：

  ListNode* temp = dummy->next;
  dummy->next = dummy->next->next;
  delete temp;

通过使用哨兵节点，我们避免了对 head 的特殊判断，删除操作变得统一且简单。

---

🧑‍💻 代码示例：

以下是使用哨兵节点的示例代码，我们将通过它来展示如何使用哨兵节点来简化插入和删除操作。

1. 定义链表节点结构：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

2. 插入操作：

void insertAtHead(ListNode*& head, int val) {
    ListNode* dummy = new ListNode(-1); // 哨兵节点
    dummy->next = head;  // 连接哨兵节点与原链表

    ListNode* newNode = new ListNode(val);  // 创建新的节点
    newNode->next = dummy->next;  // 新节点指向原链表的头节点
    dummy->next = newNode;  // 将哨兵节点的指针指向新的节点

    head = dummy->next;  // 更新链表的头节点
    delete dummy;  // 删除哨兵节点
}

• 在这个例子中，我们通过 哨兵节点，避免了特殊判断头节点为空或不为空的复杂逻辑。

3. 删除操作：

void deleteNode(ListNode*& head, int val) {
    ListNode* dummy = new ListNode(-1);  // 哨兵节点
    dummy->next = head;  // 连接哨兵节点与原链表

    ListNode* current = dummy;
    while (current->next != nullptr && current->next->val != val) {
        current = current->next;  // 找到待删除节点的前一个节点
    }

    if (current->next != nullptr) {  // 找到了要删除的节点
        ListNode* temp = current->next;
        current->next = current->next->next;  // 删除节点
        delete temp;  // 释放节点内存
    }

    head = dummy->next;  // 更新链表的头节点
    delete dummy;  // 删除哨兵节点
}

• 在删除操作中，哨兵节点的存在让我们不需要单独处理删除头节点的情况，代码更加简洁和一致。

4. 遍历打印链表：

void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        cout << current->val << " -> ";
        current = current->next;
    }
    cout << "null" << endl;
}

5. 使用示例：

int main() {
    ListNode* head = nullptr;

    insertAtHead(head, 1);  // 插入 1
    insertAtHead(head, 2);  // 插入 2
    insertAtHead(head, 3);  // 插入 3

    printList(head);  // 输出 3 -> 2 -> 1 -> null

    deleteNode(head, 2);  // 删除节点 2

    printList(head);  // 输出 3 -> 1 -> null

    return 0;
}

📝 总结：

• 哨兵节点是链表操作中一种非常有用的技巧，它简化了对链表头节点的操作，避免了空链表、头节点或尾节点的特殊判断。
• 它可以使得链表的插入、删除操作变得更加统一和简洁，特别是在删除头节点时，它非常有效。
• 哨兵节点通常不会出现在链表的有效数据中，它的值常常是一个占位符，不参与实际的数据存储。

所谓哨兵，就是增加了一个前置条件，就好像门卫一样