数据结构与算法 带表头结点的单链表

带表头结点的单链表是一种常见的链表实现方式，它在链表头部额外添加了一个特殊的结点作为表头，用于简化链表的操作。

表头结点的数据域可以为空，或者存储一些表示链表长度或其他信息的值。而表头结点的指针域则指向链表的第一个有效结点。

下面是一个示例代码来创建带表头结点的单链表：

#include <iostream>

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

class LinkedList {
public:
    LinkedList() {
        head = new ListNode(0);  // 创建表头结点，其值为0
    }

    void insert(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = head->next;
        head->next = newNode;
    }

    void remove(int val) {
        ListNode* prev = head;
        ListNode* curr = head->next;
        while (curr) {
            if (curr->val == val) {
                prev->next = curr->next;
                delete curr;
                break;
            }
            prev = curr;
            curr = curr->next;
        }
    }

    void display() {
        ListNode* curr = head->next;
        while (curr) {
            std::cout << curr->val << " ";
            curr = curr->next;
        }
        std::cout << std::endl;
    }

private:
    ListNode* head;
};

使用示例：

int main() {
    LinkedList list;
    list.insert(3);
    list.insert(5);
    list.insert(2);
    list.insert(7);
    list.display();  // 输出: 7 2 5 3

    list.remove(5);
    list.display();  // 输出: 7 2 3

    return 0;
}