实现单链表的基本操作

单链表是一种常见的数据结构，其基本操作包括以下几个：

1. 初始化链表：创建一个空链表，即没有任何节点。
2. 插入节点：在链表中插入一个新节点，可以在链表头部、尾部或者中间插入。
3. 删除节点：从链表中删除一个节点，可以删除链表头部、尾部或者中间的节点。
4. 遍历链表：遍历整个链表，访问每个节点的值或者执行其他操作。

以下是单链表的基本操作实现的示例代码：

//定义链表节点结构体
struct ListNode {
    int val; // 节点值
    ListNode *next; // 下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {} // 构造函数
};

// 初始化链表
ListNode* initList() {
    ListNode *head = new ListNode(0); // 创建一个头节点，值为0
    return head;
}

// 插入节点
void insertNode(ListNode *head, int val) {
    ListNode *newNode = new ListNode(val); // 创建一个新节点
    newNode->next = head->next; // 将新节点的next指针指向头节点的下一个节点
    head->next = newNode; // 将头节点的next指针指向新节点
}

// 删除节点
void deleteNode(ListNode *head, int val) {
    ListNode *p = head;
    while (p->next != NULL) { // 遍历链表
        if (p->next->val == val) { // 找到要删除的节点
            ListNode *tmp = p->next;
            p->next = p->next->next; // 将前一个节点的next指针指向当前节点的下一个节点
            delete tmp; // 释放节点内存
            break;
        }
        p = p->next;
    }
}

// 遍历链表
void traverseList(ListNode *head) {
    ListNode *p = head->next; // 从第一个节点开始遍历
    while (p != NULL) {
        // 访问节点值或执行其他操作
        cout << p->val << " ";
        p = p->next;
    }
}

需要注意的是，在插入和删除节点时，需要遍历链表找到要插入或删除的节点，时间复杂度为O(n)。如果需要频繁地在链表中插入或删除节点，可以考虑使用其他数据结构，如双向链表或者跳表。