手写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 <- 4Node* 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 <- 4Node* 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;
}

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

视频集中存储EasyCVR平台播放一段时间后出现黑屏是什么原因?该如何解决?

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…

jsvascript使用dhtmlXTreeObject的loadJSONObject绘制目录树

文章目录 1&#xff0c;引入dhtmlXTreeObject的css和js文件2&#xff0c;创建一棵目录树2.1&#xff0c;let tree new dhtmlXTreeObject(id-dhtmltree-0, "100%", "100%", 0);2.2&#xff0c;设置图片根目录&#xff08;后续使用到的图片都是相对于该目录…

JavaEE初阶学习:JVM(八股文)

1.JVM 中的内存区域划分 JVM 其实是一个Java进程~ java 进程会从操作系统这里申请一大块内存区域,给java代码使用~ 内存区域进一步划分,给出不同的用途 1.堆 new 出来的对象 (成员变量) 2.栈 维护方法之间的调用关系 (局部变量) 3.方法区(旧) / 元数据区 (新) 放的是类加载之…

Python语法基础(变量 注释 数据类型 输入与输出 运算符 缩进)

目录 变量变量命名规则变量的类型变量的创建变量的作用域 注释的方法数据类型对象和引用的概念Number(数字)数据转换 输入与输出输入函数输出函数输出函数的end参数输出格式多行语句 运算符算术运算符赋值运算符三目运算符运算符的优先级 缩进缩进格式注意事项层级嵌套 变量 标…

【计算机网络】HTTPS

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

MES系统如何赋能制造企业实现4M防错追溯?

生产过程4M管理和MES系统的结合是现代制造业中关键的质量管理实践&#xff0c;它有助于提高生产效率、降低生产成本并保证产品质量。本文将深入探讨4M管理的概念&#xff0c;以及MES系统如何赋能制造企业实现4M防错追溯。 一、4M管理的概念 4M管理是指在制造过程中管理和控制四…

uni-app——項目day01

配置uni-app開發環境 uni-app快速上手 | uni-app官网 创建项目 图中四个划线就是要配置的地方. 选择vue2还是vue3看个人选择。 目录结构 但是现在新版本创建的项目已经没有components目录了&#xff0c;需要自己创建。 项目运行到微信开发者工具 使用git管理项目 node-mod…

webGL项目的开发流程

WebGL (Web Graphics Library) 是一种用于在网页上渲染 2D 和 3D 图形的 JavaScript API。下面是创建 Web 应用程序中使用 WebGL 的流程&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 了解 WebGL&am…

Docker 安装 MySQL

目录 一、查看 MySQL 版本 二、拉取 MySQL 镜像 三、查看本地镜像 四、运行容器 五、停止和启动容器 六、列出正在运行的容器 七、进入容器 八、登录MySQL 九、IDEA 连接 MySQL 一、查看 MySQL 版本 访问 MySQL 镜像库地址&#xff1a;https://hub.docker.com/_/mysq…

ceph-deploy bclinux aarch64 ceph 14.2.10

ssh-copy-id&#xff0c;部署机免密登录其他三台主机 所有机器硬盘配置参考如下&#xff0c;计划采用vdb作为ceph数据盘 下载ceph-deploy pip install ceph-deploy 免密登录设置主机名 hostnamectl --static set-hostname ceph-0 .. 3 配置hosts 172.17.163.105 ceph-0 172.…

华为防火墙vrrp+hrp双机热备主备备份(两端为交换机)

默认上下来全两个vrrp主都是左边 工作原理&#xff1a; vrrp刚开机都是先initialize状态&#xff0c;然后切成active或standb状态。 hrp使用18514端口&#xff0c;且用的单播&#xff0c;要策略放行&#xff0c;由主设备发hrp心跳报文 如果设备为acitve状态时自动优先级为65…

mysql基础 --子查询

文章目录 子查询 子查询 一个查询语句&#xff0c;嵌套在另一个查询语句内部&#xff1b;子查询先执行&#xff0c;其结果被外层主查询使用&#xff1b;子查询放入括号内&#xff1b;子查询放在比较条件的右侧&#xff1b;子查询返回一条&#xff0c;为单行子查询&#xff1b;…

Flutter 实战:构建跨平台应用

文章目录 一、简介二、开发环境搭建三、实战案例&#xff1a;开发一个简单的天气应用1. 项目创建2. 界面设计3. 数据获取4. 实现数据获取和处理5. 界面展示6. 添加动态效果和交互7. 添加网络错误处理8. 添加刷新功能9. 添加定位功能10. 添加通知功能11. 添加数据持久化功能 《F…

刚学C语言太无趣 推荐一个好用易学的可视化框架:EasyX。VC6.0就能写

很多同学在大一刚学C语言时&#xff0c;是不是很好奇为什么别人编程都在做软件&#xff0c;而自己只能面对着黑窗口进行 printf &#xff1f; EasyX&#xff0c;C语言可视化编程。 分享我大一时候做的一个项目&#xff0c;用 VC6.0 开发的一款画图软件&#xff1a; 这个软件源…

分享76个Python管理系统源代码总有一个是你想要的

分享76个Python管理系统源代码总有一个是你想要的 学习知识费力气&#xff0c;收集整理更不易。 知识付费甚欢喜&#xff0c;为咱码农谋福利。 下载链接&#xff1a;https://pan.baidu.com/s/1JtcEHG9m8ro4-dc29kVyDg?pwd8888 提取码&#xff1a;8888 项目名称 A simpl…

计蒜客详解合集(2)期

目录 T1126——单词倒排 T1617——地瓜烧 T1612——蒜头君的数字游戏 T1488——旋转单词 T1461——校验信用卡号码 T1437——最大值和次大值 T1126——单词倒排 超级水的一道题&#xff0c;和T1122类似但更简单&#xff0c;分割后逆序输出即可~ 编写程序&#xff0c;读入…

Python---练习:把8名讲师随机分配到3个教室

案例&#xff1a;把8名讲师随机分配到3个教室 列表嵌套&#xff1a;有3个教室[[],[],[]]&#xff0c;8名讲师[A,B,C,D,E,F,G,H]&#xff0c;将8名讲师随机分配到3个教室中。 分析&#xff1a; 思考1&#xff1a;我们第一间教室、第二间教室、第三间教室&#xff0c;怎么表示…

C# .NET Core API Controller以及辅助专案

准备工作 Windows 10Visual Studio 2019(2017就有可以集中发布到publish目录的功能了吧)C#将方法封装(据说可以提高效率,就像是我们用的dll那种感觉新增专案作为我们API的辅助专案(作用类似dll&#xff0c;此处&#xff0c;你也可以在你自己的API专案里建文件夹&#xff0c;但…

什么是UV贴图?

UV 是与几何图形的顶点信息相对应的二维纹理坐标。UV 至关重要&#xff0c;因为它们提供了表面网格与图像纹理如何应用于该表面之间的联系。它们基本上是控制纹理上哪些像素对应于 3D 网格上的哪个顶点的标记点。它们在雕刻中也很重要。 为什么UV映射很重要&#xff1f; 默认情…

网络层+数据链路层+物理层

一)网络层协议: 一)IP协议报头介绍: 咱们的IP协议能够在两点之间规划处一条合适的路径&#xff0c;什么叫做合适&#xff1f;那就得看咱们的TOS是怎么进行选的&#xff0c;比如说选择最大吞吐量&#xff0c;咱们就需要进行选择一个最大的带宽路径&#xff1b; 16位总长度:IP数据…