C/C++ 双链表之逆序的实例详解

本文将详细讲解如何使用 C/C++ 实现双链表的逆序操作，以及具体实现代码的细节。在这篇文章中，我们将会介绍双链表的概念以及如何实现双链表的逆序操作。

双链表的概念

双链表是一种链式存储数据的结构，它类似于单向链表，但每个节点有两个指针分别指向该节点的前驱节点和后继节点。由于它的链式存储结构，双链表灵活、高效，在许多应用场景中都被广泛使用。

双链表的逆序操作

双链表的逆序操作是将双链表的存储顺序从原来的正序调整为逆序的一种操作。在实际应用中，逆序操作也被广泛使用，它可以用于实现链式结构的反转、实现栈等其他数据结构。

下面是代码示例：

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

ListNode* reverseList(ListNode* head) {
    ListNode* curr = head;
    ListNode* prev = NULL;
    while (curr != NULL) {
        ListNode* next = curr->next;
        curr->next = prev;
        curr->prev = next; // 注意此处的修改，将 prev 指向 next 节点
        prev = curr;
        curr = next;
    }
    return prev;
}

在上面的代码中，我们定义了一个结构体 ListNode 表示双链表节点的数据结构，它包含三个成员变量：一个 val 表示该节点存储的值，以及两个指针 prev、next 分别指向该节点的前驱节点和后继节点。

我们还实现了一个名为 reverseList 的函数，该函数用于实现双链表的逆序操作。该函数的参数为指向链表头节点的指针 head，返回值为指向逆序后的链表头节点的指针。该函数的实现过程如下：

1. 定义两个指针 curr 和 prev，初始时分别指向链表的头节点和 NULL。
2. 遍历链表，对于遍历到的每个节点，执行以下操作：
3. 定义指针 next，将其指向当前节点的后继节点 next = curr->next。
4. 修改节点的指针，将当前节点的后继指针 curr->next 指向其前驱节点 prev，将当前节点的前驱指针 curr->prev 指向其后继节点 next。
5. 将 prev 指针指向当前节点 prev = curr。
6. 将 curr 指针指向下一个节点 curr = next。
7. 遍历结束后，返回 prev 指针即为逆序后的链表头节点。

代码示例

下面是一个完整的代码示例，包含了链表的创建、打印、插入、删除、查找和逆序等常用操作。

#include <iostream>
using namespace std;

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

class List {
public:
    List() {
        head = new ListNode(0);
        tail = new ListNode(0);
        head->next = tail;
        tail->prev = head;
    }

    ~List() {
        ListNode* curr = head;
        while (curr != NULL) {
            ListNode* next = curr->next;
            delete curr;
            curr = next;
        }
    }

    void print() {
        ListNode* curr = head->next;
        while (curr != tail) {
            cout << curr->val << " ";
            curr = curr->next;
        }
        cout << endl;
    }

    void insert(int val) {
        ListNode* node = new ListNode(val);
        node->prev = tail->prev;
        node->next = tail;
        tail->prev->next = node;
        tail->prev = node;
    }

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

    ListNode* find(int val) {
        ListNode* curr = head->next;
        while (curr != tail) {
            if (curr->val == val) {
                return curr;
            }
            curr = curr->next;
        }
        return NULL;
    }

    void reverse() {
        ListNode* curr = head->next;
        ListNode* prev = NULL;
        while (curr != tail) {
            ListNode* next = curr->next;
            curr->next = prev;
            curr->prev = next; // 注意此处的修改，将 prev 指向 next 节点
            prev = curr;
            curr = next;
        }
        head->next = prev;
        prev->prev = head;
    }

private:
    ListNode* head;
    ListNode* tail;
};

int main() {
    List list;
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.insert(4);
    list.insert(5);
    cout << "原链表：" << endl;
    list.print();
    list.remove(3);
    cout << "删除节点 3 后的链表：" << endl;
    list.print();
    ListNode* node = list.find(2);
    cout << "查找节点 2：" << endl;
    cout << node->val << endl;
    cout << "逆序后的链表：" << endl;
    list.reverse();
    list.print();
    return 0;
}

在上面的代码中，我们定义了一个名为 List 的链表类，该类封装了链表的创建、打印、插入、删除、查找和逆序等常用操作。通过该类，我们可以轻松地实现链表的基本功能。

总结

本文详细介绍了如何使用 C/C++ 实现双向链表的逆序操作，并提供了实现代码和相关示例。在实际应用中，逆序操作是实现链式结构的反转和栈等其他数据结构的关键操作之一。通过本文的学习，相信读者已经对双向链表和逆序操作有了更加深入的了解。