含有头结点的链表c++初始化

在C++中，含有头节点的单向链表通常用于表示动态数组，它的初始化可以分为两步：创建头节点和连接节点。下面是一个简单的示例：

// 定义链表节点结构
struct ListNode {
    int val; // 节点值
    ListNode* next; // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {} // 构造函数，设置初始值和next为nullptr
};

// 初始化空链表（只有一个头节点）
ListNode* createEmptyList() {
    return new ListNode(0); // 创建一个头节点，val设为0
}

// 如果需要插入多个元素，可以在头节点之后添加
void insertToList(ListNode*& head, int value) {
    ListNode* newNode = new ListNode(value);
    newNode->next = head;
    head = newNode; // 更新头节点指向新的节点
}

在这个例子中，`createEmptyList()` 函数创建了一个含有头节点的链表，而 `insertToList()` 函数则是往链表头部追加新节点。使用链表时，你可以先调用 `createEmptyList()` 获取头节点，然后根据需要调用 `insertToList()` 添加更多元素。

相关问题

写一个带头结点单链表清空链表的C++语言

以下是清空带头结点单链表的C语言代码：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct ListNode {
    int val;                // 节点的值
    struct ListNode *next;  // 指向下一个节点的指针
} ListNode;

// 定义带头结点单链表结构体
typedef struct LinkedList {
    ListNode *head;  // 指向头结点的指针
    int size;        // 链表大小
} LinkedList;

// 初始化链表
LinkedList *initLinkedList() {
    LinkedList *list = (LinkedList *)malloc(sizeof(LinkedList));
    ListNode *head = (ListNode *)malloc(sizeof(ListNode));
    head->val = 0;
    head->next = NULL;
    list->head = head;
    list->size = 0;
    return list;
}

// 清空链表
void clearLinkedList(LinkedList *list) {
    if (list == NULL) return;
    ListNode *p = list->head->next;
    while (p != NULL) {
        ListNode *tmp = p;
        p = p->next;
        free(tmp);
    }
    list->head->next = NULL;
    list->size = 0;
}

// 主函数
int main() {
    // 初始化链表
    LinkedList *list = initLinkedList();
    
    // 在链表中添加节点
    ListNode *node1 = (ListNode *)malloc(sizeof(ListNode));
    node1->val = 1;
    node1->next = NULL;
    list->head->next = node1;
    list->size++;
    
    ListNode *node2 = (ListNode *)malloc(sizeof(ListNode));
    node2->val = 2;
    node2->next = NULL;
    node1->next = node2;
    list->size++;

    // 清空链表
    clearLinkedList(list);

    // 输出链表大小
    printf("链表大小为：%d\n", list->size); // 链表大小为：0

    return 0;
}

以上代码中，首先我们定义了链表节点的结构体 `ListNode` 和带头结点单链表的结构体 `LinkedList`。在 `initLinkedList` 函数中，我们首先动态分配了一个 `LinkedList` 类型的内存空间和一个 `ListNode` 类型的内存空间，并将头结点的值设为0，指向NULL。接着，我们将 `list->head` 指向头结点，并将链表大小初始化为0。在 `clearLinkedList` 函数中，我们首先检查链表是否为空，然后使用指针 `p` 遍历链表中的每个节点。对于每个节点，我们先使用指针 `tmp` 保存该节点的地址，然后将 `p` 指向下一个节点，并释放 `tmp` 所指向的内存空间。最后，我们将 `list->head->next` 指向NULL，并将链表大小设置为0。

在主函数中，我们首先初始化链表，然后在链表中添加了两个节点。接着，我们调用 `clearLinkedList` 函数清空链表，并输出链表的大小。注意，由于我们在 `clearLinkedList` 函数中将链表大小设置为0

以带表头结点单链表的初始化、查找、插入、删除、输出、撤销等操作编写程序实现单链表的逆置操作

以下是带表头结点单链表的逆置操作的代码实现：

#include <iostream>
using namespace std;

// 定义单链表结点结构体
struct Node {
    int data;
    Node* next;
};

// 定义单链表类
class LinkedList {
private:
    Node* head;  // 表头指针

public:
    // 构造函数
    LinkedList() {
        head = new Node;
        head->next = NULL;
    }

    // 插入结点
    void insertNode(int data) {
        Node* newNode = new Node;
        newNode->data = data;
        newNode->next = head->next;
        head->next = newNode;
    }

    // 查找结点
    Node* findNode(int data) {
        Node* p = head->next;
        while (p != NULL && p->data != data) {
            p = p->next;
        }
        return p;
    }

    // 删除结点
    void deleteNode(int data) {
        Node* p = head->next;
        Node* pre = head;
        while (p != NULL && p->data != data) {
            pre = p;
            p = p->next;
        }
        if (p != NULL) {
            pre->next = p->next;
            delete p;
        }
    }

    // 输出链表
    void printList() {
        Node* p = head->next;
        while (p != NULL) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

    // 逆置链表
    void reverseList() {
        Node* p = head->next;
        Node* pre = NULL;
        Node* next = NULL;
        while (p != NULL) {
            next = p->next;
            p->next = pre;
            pre = p;
            p = next;
        }
        head->next = pre;
    }
};

int main() {
    LinkedList list;
    list.insertNode(1);
    list.insertNode(2);
    list.insertNode(3);
    list.insertNode(4);
    list.insertNode(5);

    cout << "原链表：";
    list.printList();

    list.reverseList();

    cout << "逆置后的链表：";
    list.printList();

    return 0;
}

说明：

- 在构造函数中，创建了一个带表头结点的空链表，表头指针为 head，并将头结点的 next 指针初始化为 NULL。
- insertNode() 方法实现了向链表中插入新结点的功能。新结点的 next 指针指向原先的第一个结点，头结点的 next 指针指向新结点。
- findNode() 方法实现了查找指定数据的结点的功能，返回该结点的指针。如果未找到，则返回 NULL。
- deleteNode() 方法实现了删除指定数据的结点的功能。先利用 findNode() 方法找到该结点，然后将该结点从链表中删除，并释放该结点所占用的内存。
- printList() 方法实现了输出链表的功能。
- reverseList() 方法实现了逆置链表的功能。利用三个指针 p、pre 和 next，依次将每个结点的 next 指针指向前一个结点。最后将头结点的 next 指针指向原先的最后一个结点。