c++中链表的基本概念及使用 同时举例出链表的例题 以及反序链表的基本概念以及代码实现

链表是一种常用的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的优点是能够高效地插入和删除节点，缺点是查找节点效率较低。

链表的基本操作包括：创建链表、插入节点、删除节点、遍历链表等。

下面是一个简单的链表示例，用来存储整数：

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

void insert(ListNode*& head, int val) {
    ListNode* node = new ListNode(val);
    if (!head) {
        head = node;
        return;
    }
    ListNode* cur = head;
    while (cur->next) {
        cur = cur->next;
    }
    cur->next = node;
}

void remove(ListNode*& head, int val) {
    ListNode* cur = head;
    if (cur && cur->val == val) {
        head = head->next;
        delete cur;
        return;
    }
    while (cur && cur->next) {
        if (cur->next->val == val) {
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
            return;
        }
        cur = cur->next;
    }
}

void reverse(ListNode*& head) {
    ListNode* prev = NULL;
    ListNode* cur = head;
    while (cur) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    head = prev;
}

下面是一个例题：给定一个链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

反序链表即将链表中的节点顺序颠倒过来，可以使用迭代或递归实现。下面是一个迭代实现的例子：

void reverseList(ListNode*& head) {
    ListNode* prev = NULL;
    ListNode* cur = head;
    while (cur) {
        ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    head = prev;
}

递归实现如下：

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}