C++之单链表与双链表逆序实例(二百七十九)

简介： CSDN博客专家，专注Android/Linux系统，分享多mic语音方案、音视频、编解码等技术，与大家一起成长！

优质专栏：Audio工程师进阶系列【原创干货持续更新中……】🚀
优质专栏：多媒体系统工程师系列【原创干货持续更新中……】🚀
优质视频课程：AAOS车载系统+AOSP14系统攻城狮入门实战课【原创干货持续更新中……】🚀

人生格言： 人生从来没有捷径，只有行动才是治疗恐惧和懒惰的唯一良药.

更多原创,欢迎关注：Android系统攻城狮

欢迎关注Android系统攻城狮

🍉🍉🍉文章目录🍉🍉🍉

- 🌻1.前言
- 🌻2.单链表与双链表逆序介绍
- - 2.1.1 🐥 单链表
  - 2.1.2 🐥 双链表
  - 2.1.3 🐥 单链表的逆序
  - 2.1.3 🐥 双链表的逆序
- 🌻3.代码实例
- - 🐓3.1 单链表逆序
  - 🐓3.2 双链表逆序

🌻1.前言

本篇目的：C++之单链表与双链表逆序实例

🌻2.单链表与双链表逆序介绍

单链表和双链表是线性表的两种常见实现方式，它们在数据结构中占有重要的地位。链表通过指针将不连续的内存空间连接起来，从而实现对线性数据的存储和管理。

2.1.1 🐥 单链表

单链表是由一系列节点组成的线性集合。每个节点包含两个部分：数据域和指针域。数据域用于存储节点的数据，指针域用于存储下一个节点的地址。单链表的起始节点称为头节点，最后一个节点的指针域指向NULL。
单链表的操作主要包括节点的插入、删除和遍历。插入操作分为在头部插入、在尾部插入和在指定位置插入。删除操作分为删除头节点、删除尾节点和删除指定位置的节点。遍历操作则是从头节点开始，依次访问每个节点。

2.1.2 🐥 双链表

双链表与单链表类似，不同之处在于每个节点除了有数据域和指针域外，还有一个指向前一个节点的指针。这样，双链表的每个节点都有两个指针，分别指向前一个节点和下一个节点。双链表的起始节点同样有指向前一个节点的指针，而头节点的前一个节点指向NULL。
双链表的操作主要包括节点的插入、删除和遍历。插入操作分为在头部插入、在尾部插入和在指定位置插入。删除操作分为删除头节点、删除尾节点和删除指定位置的节点。遍历操作则是从头节点开始，依次访问每个节点。

2.1.3 🐥 单链表的逆序

单链表的逆序可以通过以下步骤实现：

创建一个新节点，将其设为当前单链表的尾节点。
遍历原单链表，每次遍历到一个新的节点，将其添加到新节点的后方。
更新新节点的指针域，使其指向原单链表的头节点。

2.1.3 🐥 双链表的逆序

双链表的逆序相比于单链表的逆序多了一个步骤，即需要同时更新前一个节点的指针。

创建一个新节点，将其设为当前双链表的尾节点。
遍历原双链表，每次遍历到一个新的节点，先更新其前一个节点的指针，使其指向新节点，然后将新节点添加到原节点的后方。
更新新节点的指针域，使其指向原双链表的头节点。

通过以上步骤，我们可以实现单链表和双链表的逆序。位域的使用可以提高数据结构的灵活性和效率，同时也能够降低内存的使用。

🌻3.代码实例

🐓3.1 单链表逆序

#include <iostream>

struct Node {
    int data;
    Node* next;
};

// 函数：单链表逆序
void reverseSingleLinkedList(Node*& head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next = nullptr;

    while (current != nullptr) {
        next = current->next; // 保存下一个节点
        current->next = prev; // 改变当前节点的指针方向
        prev = current;       // 更新前一个节点
        current = next;       // 移动到下一个节点
    }
    head = prev; // 更新头节点
}

// 函数：打印单链表
void printSingleLinkedList(const Node* head) {
    const Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = new Node{1, nullptr}; // 创建单链表
    head->next = new Node{2, nullptr};
    head->next->next = new Node{3, nullptr};
    head->next->next->next = new Node{4, nullptr};

    std::cout << "原单链表： ";
    printSingleLinkedList(head);

    reverseSingleLinkedList(head); // 逆序单链表

    std::cout << "逆序后单链表： ";
    printSingleLinkedList(head);

    // 释放内存
    Node* temp = head;
    while (temp != nullptr) {
        Node* next = temp->next;
        delete temp;
        temp = next;
    }

    return 0;
}

🐓3.2 双链表逆序

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node* prev;
};

// 函数：双链表逆序
void reverseDoubleLinkedList(Node*& head) {
    Node* prev = nullptr;
    Node* current = head;

    while (current != nullptr) {
        Node* next = current->next; // 保存下一个节点
        current->prev = next;       // 改变当前节点的指针方向
        prev = current;             // 更新前一个节点
        current = next;             // 移动到下一个节点
    }
    head = prev; // 更新头节点
}

// 函数：打印双链表
void printDoubleLinkedList(const Node* head) {
    const Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* head = new Node{1, nullptr, nullptr}; // 创建双链表
    head->next = new Node{2, nullptr, nullptr};
    head->next->prev = head;
    head->next->next = new Node{3, nullptr, nullptr};
    head->next->next->prev = head->next;
    head->next->next->next = new Node{4, nullptr, nullptr};
    head->next->next->next->prev = head->next->next;

    std::cout << "原双链表： ";
    printDoubleLinkedList(head);

    reverseDoubleLinkedList(head); // 逆序双链表

    std::cout << "逆序后双链表： ";
    printDoubleLinkedList(head);

    // 释放