手写C++ 实现链表的反转、删除、合并

目录

一、手写List成员方法

1.1 打印链表

1.2 删除链表节点

1.3 链表中倒数第k个节点

1.4 反转链表

1.5 合并两个排序链表

二、完整代码

 

一、C++实现链表成员方法

        在上一篇博客《手写链表C++》，实现了基本的List类。在面试中，经常被问到List如何反转、删除元素等，同时也为了丰富List类的成员；这一节本文实现如题等list操作。

        C++链表，一种重要的数据结构，由一系列节点构成，每个节点包含两部分：数据和指向下一个节点的指针。链表是一种物理存储单元上非连续、非顺序的存储结构，数据结构的逻辑顺序是通过链表中的指针链接次序实现的。链表的最简单形式是单向链表，它只包含一个信息域和一个指针域。链表的优点是可以动态地分配内存空间，实现高效的数据操作。在C++中，链表的每个节点都是通过指针链接在一起，从而形成一个连续的链式结构。

1.1 打印链表

为了方便debug代码，先写一个打印链表的函数：

void List::print()
{
    if (size_ == 0)
    {
        cout << "size = 0" << endl;
        return;
    }
    //遍历
    Node* p_curr = head_->next_;//【注意这里next】
    while (p_curr != nullptr)
    {
        cout << p_curr->data_ << " ";
        p_curr = p_curr->next_;
    }
    cout << endl;
}

1.2 删除链表节点

思想就是找到要删除的Node的前一个节点，让前一个节点的指针指向Node的下一个节点就行了。

例如：pos = 3的时候，for循环执行完毕，p_curr表示索引值为2的节点地址，接着我们让p_curr->next 指向 下一个节点的下一个节点。

//功能：删除索引位置为pos的节点
void List::remove(int pos)
{
    if (pos < 0 || pos > size_)
    {
        return;
    }
    Node* p_curr = head_;
    for (int i = 0; i < pos; i++)// 3
    {
        p_curr = p_curr->next_;
    }
    p_curr->next_ = p_curr->next_->next_;
    size_--;
}

1.3 链表中倒数第k个节点

你可以去看看剑指offer上的做法，我这里类List维护了一个size_，所以比较简单。

//链表中倒数第k个节点
int List::get_reverse_element(int reverse_pos)
{
    int pos = size_ - reverse_pos;
    Node* p_curr = head_;
    for (int i = 0; i < pos; i++)
    {
        p_curr = p_curr->next_;
    }
    return p_curr->data_;
}

1.4 反转链表

这个方法是必学的，因为面试中经常问，甚至需要现场手撕。

//反转链表
void List::reverse()
{
    // head   -> 1 -> 2 -> 3 -> 4 -> nullptr
    //nullptr <- 1 <- 2 <- 3 <- 4

    Node* p_curr = head_->next_;
    Node* p_prev = nullptr;
    while (p_curr != nullptr)
    {
        Node* p_next = p_curr->next_;
        if (p_next == nullptr)
        {
            head_->next_ = p_curr;
        }
        p_curr->next_ = p_prev;
        p_prev = p_curr;
        p_curr = p_next;
    }
}

下图是反转效果：

ec73148a7a4b46bf85b735c511905637.png

1.5 合并两个排序链表

//合并两个排序链表
void mergeLists(List& list3, List& list4, List& list34)
{
    Node* p_curr3 = list3.head_->next_;
    Node* p_curr4 = list4.head_->next_;
    Node* p_curr34 = list34.head_->next_;
    int location = 0;
    while ((p_curr3 != nullptr) || (p_curr4 != nullptr))
    {
        if ((p_curr3 != nullptr) && (p_curr4 != nullptr))
        {
            if (p_curr3->data_ < p_curr4->data_)
            {
                list34.insert(location, p_curr3->data_);
                location++;
                list34.insert(location, p_curr4->data_);
                location++;
            }
            else
            {
                list34.insert(location, p_curr4->data_);
                location++;
                list34.insert(location, p_curr3->data_);
                location++;
            }
            p_curr3 = p_curr3->next_;
            p_curr4 = p_curr4->next_;
        }
        else if ((p_curr3 != nullptr) && (p_curr4 == nullptr))
        {
            list34.insert(location, p_curr3->data_);
            location++;
            p_curr3 = p_curr3->next_;
        }
        else if ((p_curr3 == nullptr) && (p_curr4 != nullptr))
        {
            list34.insert(location, p_curr4->data_);
            location++;
            p_curr4 = p_curr4->next_;
        }
    }
}

例如现在有两个升序序列：

  • A：0 2 4 6 8 14                                                                                                       
  • B：1 3 5 7 9 12 21 31 

要将他们变成一个生序序列；

思路：假设现在两个序列元素个数相等；我们将 0 1对比将得到 0 1， 再将1和2 3 对比 得到 0 1 2 3；再将3和4 5 对比；依次类推，（对应第10行代码）

现在考虑 A序列长度 > B序列长度；对应第29行代码； A序列长度 < B序列长度；对应上述第35行代码。

//合并两个排序链表
    List list3,list4;
    for (int i = 0; i < 5; i++)
    {
        list3.insert(i, 2*i);
        list4.insert(i, 2 * i + 1);
    }
    list3.insert(5, 14);
    list4.insert(5, 12);
    list4.insert(6, 21);
    list4.insert(7, 31);
    list3.print();
    list4.print();

    List list34;
    mergeLists(list3, list4, list34);
    list34.print();

测试用例：

216e44bc448d4c09785c6037589f395b.jpeg

二、链表完整代码

以下代码包含：List的实现，节点定义，链表的插入、删除、合并、反转等。

#include<iostream>
using namespace std;

class Node
{
public:
    int data_;//数据阈
    Node* next_;//指针阈
public:
    Node() :data_(-1), next_(nullptr) {}
};

class List
{
public:
    List()
    {
        this->head_ = new Node();// 不分配空间，下面赋值是不合理的！
                                 //this->head_->data_ = 0;//多余？
        this->head_->next_ = nullptr;
        this->size_ = 0;
    };
    void insert(int pos, int value);
    void remove(int pos);
    int get_reverse_element(int reverse_pos);//链表中倒数第k个节点
    void reverse();

    int operator[](int i);
    void print();
    ~List();
public:
    Node* head_;
    int size_;//维护一个size
};
//在第pos个元素前一个位置插入（创建、找到位置、入链表）
void List::insert(int pos, int value)
{
    if (pos < 0 || pos > size_)
        return;

    //创建新的节点接受数据
    Node* newnode = new Node();
    newnode->data_ = value;
    //cout << "newnode->data_ = " << *newnode->data_ << endl;
    newnode->next_ = nullptr;

    //利用辅助指针找到pos前一个节点
    // 其实这里不断next，无非就是希望p_curr = nullptr
    // 然后56行 让newnode->next_  = nullptr（这个nullptr是从head_->next 传过来的）；也就是尾部插入嘛
    // 而循环链表 同理 让newnode->next_  = &(head_)（这个 &(head_) 是从head_->next 传过来的）；
    Node* p_curr = head_;
    for (int i = 0; i < pos; i++) //这个for循环本质上是head_->next_->next_......
    {
        p_curr = p_curr->next_;
    }
    //现在p_curr就是pos前一个节点的指针阈
    //新节点入链表
    newnode->next_ = p_curr->next_;//右边
    p_curr->next_ = newnode;//左边
    size_++;
}

void List::remove(int pos)
{
    if (pos < 0 || pos > size_)
    {
        return;
    }
    Node* p_curr = head_;
    for (int i = 0; i < pos; i++)// 3
    {
        p_curr = p_curr->next_;
    }
    p_curr->next_ = p_curr->next_->next_;
    size_--;
}

//链表中倒数第k个节点
int List::get_reverse_element(int reverse_pos)
{
    int pos = size_ - reverse_pos;
    Node* p_curr = head_;
    for (int i = 0; i < pos; i++)
    {
        p_curr = p_curr->next_;
    }
    return p_curr->data_;
}

//反转链表
void List::reverse()
{
    // head   -> 1 -> 2 -> 3 -> 4 -> nullptr
    //nullptr <- 1 <- 2 <- 3 <- 4

    Node* p_curr = head_->next_;
    Node* p_prev = nullptr;
    while (p_curr != nullptr)
    {
        Node* p_next = p_curr->next_;
        if (p_next == nullptr)
            if (p_curr->next_ == nullptr)
            {
                head_->next_ = p_curr;
            }
        p_curr->next_ = p_prev;
        p_prev = p_curr;
        p_curr = p_next;
    }
}

int List::operator[](int i)
{
    Node* p_curr = head_;
    int count = 0;
    while (count <= i)
    {
        p_curr = p_curr->next_;
        count++;
    }
    return p_curr->data_;
}
void List::print()
{
    if (size_ == 0)
    {
        cout << "size = 0" << endl;
        return;
    }
    //遍历
    Node* p_curr = head_->next_;//【注意这里next】
    while (p_curr != nullptr)
    {
        cout << p_curr->data_ << " ";
        p_curr = p_curr->next_;
    }
    cout << endl;
}
List::~List()
{
    while (size_ != 0)
    {
        Node* p_curr = head_;
        for (int i = 0; i < (size_ - 1); i++)// 012345 i < 5
        {
            p_curr = p_curr->next_;//for循环执行完，p_curr指向4
        }
        delete p_curr->next_;//删除最后一个元素
        p_curr->next_ = nullptr;//末尾元素 空指针
        size_--;
        print();
    }
    delete head_; //【这个容易忘记！】
    cout << "delete!" << endl;
}

//合并两个排序链表
void mergeLists(List& list3, List& list4, List& list34)
{
    Node* p_curr3 = list3.head_->next_;
    Node* p_curr4 = list4.head_->next_;
    Node* p_curr34 = list34.head_->next_;
    int location = 0;
    while ((p_curr3 != nullptr) || (p_curr4 != nullptr))
    {
        if ((p_curr3 != nullptr) && (p_curr4 != nullptr))
        {
            if (p_curr3->data_ < p_curr4->data_)
            {
                list34.insert(location, p_curr3->data_);
                location++;
                list34.insert(location, p_curr4->data_);
                location++;
            }
            else
            {
                list34.insert(location, p_curr4->data_);
                location++;
                list34.insert(location, p_curr3->data_);
                location++;
            }
            p_curr3 = p_curr3->next_;
            p_curr4 = p_curr4->next_;
        }
        else if ((p_curr3 != nullptr) && (p_curr4 == nullptr))
        {
            list34.insert(location, p_curr3->data_);
            location++;
            p_curr3 = p_curr3->next_;
        }
        else if ((p_curr3 == nullptr) && (p_curr4 != nullptr))
        {
            list34.insert(location, p_curr4->data_);
            location++;
            p_curr4 = p_curr4->next_;
        }
    }
}

int main()
{
    List list1;
    //插入
    for (int i = 0; i < 15; i++)
    {
        list1.insert(i, i);
    }
    //删除
    list1.remove(10);
    list1.remove(5);
    //打印
    list1.print();
    list1.reverse();
    list1.print();
    //访问倒数元素
    for (int i = 1; i < 4; i++)
    {
        cout << "倒数第" << i << "个元素是：" << list1.get_reverse_element(i) << endl;
    }
    list1.insert(2, 9999);
    //重载符[]
    for (int i = list1.size_ - 1; i >= 0; i--)
    {
        cout << list1[i] << " ";
    }
    cout << endl;
    List list2;
    list2.insert(0, 10);
    list2.insert(1, 20);
    list2.insert(2, 30);
    list2.print();
    int size2 = list2.size_;
    //合并两个排序链表
    List list3, list4;
    for (int i = 0; i < 5; i++)
    {
        list3.insert(i, 2 * i);
        list4.insert(i, 2 * i + 1);
    }
    list4.insert(5, 12);
    list4.insert(6, 21);
    list3.print();
    list4.print();
    List list34;
    mergeLists(list3, list4, list34);
    list34.print();
    return 1;
}

 

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/131722.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

ROS 学习应用篇（二）话题Topic学习之话题的发布与订阅

ROS 学习应用篇（二）话题Topic学习之话题的发布与订阅

顾名思义&#xff0c;这是一个异步的消息传达过程 首先是消息的发布&#xff0c;接着是消息的订阅 话题发布 由发布者发布一个“消息”的数据结构&#xff0c;再由订阅者订阅这个消息结构。 再开始撰写一段程序之前&#xff0c;我们需要在程序代码中引入库→节点初始化→创…
阅读更多...
合成数据加速机器视觉学习

合成数据加速机器视觉学习

虽然机器学习在基于视觉的自动化中的应用正在增长&#xff0c;但许多行业都面临着挑战&#xff0c;并难以在其计算机视觉应用中实施它。这在很大程度上是由于需要收集许多图像&#xff0c;以及与准确注释这些图像中的不同产品相关的挑战。 该领域的最新趋势之一是利用合成数据…
阅读更多...
【Github】git clone命令下载文件中途停止

【Github】git clone命令下载文件中途停止

方法一&#xff1a; 使用git clone命令下载github上的源代码时&#xff0c;有时文件下载到一定百分比时就停止不动&#xff0c; 这是因为我们所下载的文件很大&#xff0c;超过了git预先分配的Postbuffer容量&#xff0c;所以一直卡在那里。可以使用以下命令查看当前Postbuffe…
阅读更多...
景联文科技加入中国人工智能产业发展联盟（AIIA），与行业各方共促AI产业发展

景联文科技加入中国人工智能产业发展联盟（AIIA），与行业各方共促AI产业发展

近日&#xff0c;景联文科技加入中国人工智能产业发展联盟&#xff08;AIIA&#xff09;&#xff0c;与行业各方共同挖掘人工智能数据的更多价值&#xff0c;破解中国人工智能AI数据短缺难题。 中国人工智能产业发展联盟&#xff08;简称AIIA&#xff09;是在国家发改委、科技部…
阅读更多...
省钱攻略：三大运营商保号套餐办理攻略，不再当冤大头！

省钱攻略：三大运营商保号套餐办理攻略，不再当冤大头！

现在的朋友都是相当的聪明&#xff0c;都不想直接在营业厅办理套餐&#xff0c;而是选择保号套餐流量卡。 今天&#xff0c;小编主要介绍的就是三大运营商的保号套餐&#xff0c;以及如何办理&#xff01; 如图所示&#xff1a; ​　　电信最低可改5元套餐&#xff0c;移动、联…
阅读更多...
计蒜客详解合集（2）期

计蒜客详解合集（2）期

目录 T1126——单词倒排 T1617——地瓜烧 T1612——蒜头君的数字游戏 T1488——旋转单词 T1461——校验信用卡号码 T1437——最大值和次大值 T1126——单词倒排 超级水的一道题&#xff0c;和T1122类似但更简单&#xff0c;分割后逆序输出即可~ 编写程序&#xff0c;读入…
阅读更多...
51单片机PCF8591数字电压表数码管显示设计( proteus仿真+程序+设计报告+讲解视频）

51单片机PCF8591数字电压表数码管显示设计( proteus仿真+程序+设计报告+讲解视频）

PCF8591数字电压表数码管显示 1.主要功能&#xff1a;讲解视频&#xff1a;2.仿真3. 程序代码4. 设计报告5. 设计资料内容清单&&下载链接资料下载链接&#xff08;可点击&#xff09;&#xff1a; 51单片机PCF8591数字电压表数码管设计( proteus仿真程序设计报告讲解视…
阅读更多...
收藏！7个国内「小众」的程序员社区

收藏！7个国内「小众」的程序员社区

技术社区是大量开发者的集聚地&#xff0c;在技术社区可以了解到行业的最新进展&#xff0c;学习最前沿的技术&#xff0c;认识有相同爱好的朋友&#xff0c;在一起学习和交流。 国内知名的技术社区有CSDN、博客园、开源中国、51CTO&#xff0c;还有近两年火热的掘金&#xff…
阅读更多...
【Kurbernetes集群】Pod资源、Pod资源限制和Pod容器的健康检查（探针）详解

【Kurbernetes集群】Pod资源、Pod资源限制和Pod容器的健康检查（探针）详解

Pod资源 一、Pod概述1.1 Pod的定义1.2 一个Pod能包含几个容器&#xff1f;1.3 Pod的分类1.3.1 控制器管理的Pod1.3.2 自主式Pod1.3.3 静态Pod 1.4 Pod中容器的分类1.4.1 Pause容器1.4.2 初始化容器1.4.3 应用容器 1.5 Pod常见的状态 二、Pod中的策略2.1 镜像拉取策略2.2 Pod中容…
阅读更多...
【计算机网络】HTTPS

【计算机网络】HTTPS

文章目录 前言为什么会出现 HTTPSHTTPS 是如何进行加密的1. 对称加密非对称加密中间人攻击3. 引入证书 前言 前面我们学习了应用层中使用比较常见的 HTTP 协议&#xff0c;但是呢&#xff1f;在实际的使用中&#xff0c;浏览器和服务器之间的通信其实很少使用到 HTTP&#xff…
阅读更多...
Google Firebase PHP实现消息推送

Google Firebase PHP实现消息推送

获取key的方法&#xff1a; 登录谷歌开发者后台 https://console.firebase.google.com/?hlzh-cn function firebaseNotice($title,$body){$token_arr[token1,token2]; //用户的firebasetoken列表$notify_msg ["notification" > ["title" > $title…
阅读更多...
C++入门 1——命名空间，缺省参数

C++入门 1——命名空间，缺省参数

C入门 一.前言二.命名空间2.1命名空间的定义2.2命名空间的使用 三.C的输入&输出四.缺省参数4.1概念4.2缺省分类 五.函数重载5.1概念5.2函数重载条件及代码 六.引用6.1概念6.2引用特性6.3常引用6.4使用6.5引用和指针的区别和联系 七.内联函数7.1概念7.2特性 一.前言 今天就…
阅读更多...
[ Linux Busybox ] nandwrite 命令解析

[ Linux Busybox ] nandwrite 命令解析

文章目录 相关结构体nandwrite 函数实现nandwrite 实现流程图 文件路径&#xff1a;busybox-1.20.2/miscutils/nandwrite.c 相关结构体 MTD 相关信息结构体 struct mtd_info_user {__u8 type; // MTD 设备类型__u32 flags; // MTD设备属性标志__u32…
阅读更多...
（免费版？）CLion Nova 强势登陆 C 和 C++ 开发领域

（免费版？）CLion Nova 强势登陆 C 和 C++ 开发领域

系列文章目录 文章目录 系列文章目录前言一、CLion Nova二、目标三、优势和改进四、显著差异五、如何安装 CLion Nova六、分享您的反馈意见总结 阿纳斯塔西娅-卡扎科娃 2023 年 11 月 9 日 前言 今天&#xff0c;我们宣布推出免费的 CLion 早期预览版&#xff0c;它使用 ReSh…
阅读更多...
400G OSFP SR8光模块最新解决方案

400G OSFP SR8光模块最新解决方案

数字化时代&#xff0c;意味着网络速度、能效和成本成为数据中心和通信网络关注的焦点。为了满足这些需求不断催生和进化新的产品&#xff0c;因此在这一背景下400G OSFP SR8光模块最新解决方案成为了很好的助力。该方案不仅提高了网络速度&#xff0c;还实现了节能降耗&#x…
阅读更多...
ARM 基础学习记录 / ARM 裸机编程

ARM 基础学习记录 / ARM 裸机编程

汇编程序调用 C 程序详情 在 C 程序和 ARM 汇编程序之间相互调用时必须遵守 ATPCS 规则&#xff0c;其是基于 ARM 指令集和 THUMB 指令集过程调用的规范&#xff0c;规定了调用函数如何传递参数&#xff0c;被调用函数如何获取参数&#xff0c;以何种方式传递函数返回值。 寄存…
阅读更多...
95. 费解的开关

95. 费解的开关

题目 思路 因为最优解是每个灯只操作一次所以顺序无所谓只要确定了第一行后&#xff0c;下面都可以确定当前灯不亮就操作它下面的格子即可点亮它我觉得这种方法是唯一不会互相干扰的方法还是不太理解… 代码 #include <cstdio> #include <cmath> #include <c…
阅读更多...
2023最新版本 从零基础入门C++与QT（学习笔记） -1- C++输入与输出

2023最新版本 从零基础入门C++与QT（学习笔记） -1- C++输入与输出

&#x1f38f;说在前面 &#x1f388;我预计是使用两个月的时间玩转C与QT &#x1f388;所以这是一篇学习笔记 &#x1f388;根据学习的效率可能提前完成学习,加油&#xff01;&#xff01;&#xff01; 输入(代码如下方代码块) &#x1f384;分析一下构成 &#x1f388;…
阅读更多...
Rocksdb LSM Tree Compaction策略

Rocksdb LSM Tree Compaction策略

RocksDB读写简介 直接画图说明。这张图取自Flink PMC大佬Stefan Richter在Flink Forward 2018演讲的PPT&#xff0c;笔者重画了一下。 RocksDB的写缓存&#xff08;即LSM树的最低一级&#xff09;名为memtable&#xff0c;对应HBase的MemStore&#xff1b;读缓存名为block cac…
阅读更多...
CV计算机视觉每日开源代码Paper with code速览-2023.11.8

CV计算机视觉每日开源代码Paper with code速览-2023.11.8

精华置顶 墙裂推荐&#xff01;小白如何1个月系统学习CV核心知识&#xff1a;链接 点击CV计算机视觉&#xff0c;关注更多CV干货 论文已打包&#xff0c;点击进入—>下载界面 点击加入—>CV计算机视觉交流群 1.【基础网络架构】&#xff08;WACV2024&#xff09;SBCFo…
阅读更多...
最新文章

Copyright @ 2022~2023