数据结构:链表基础OJ练习+带头双向循环链表的实现
目录
一.leetcode剑指 Offer II 027. 回文链表
1.问题描述
2.问题分析与求解
(1) 快慢指针法定位链表的中间节点
(2) 将链表后半部分进行反转
附:递归法反转链表
(3) 双指针法判断链表是否回文
二.带头双向循环链表的实现
1.头文件
2.节点内存申请接口和链表初始化接口
3.链表的打印和查找接口
4.链表的增删接口
5.链表销毁接口
一.leetcode剑指 Offer II 027. 回文链表
剑指 Offer II 027. 回文链表 - 力扣(Leetcode)
1.问题描述
给定一个链表的头节点
head,
请判断其是否为回文链表。(是回文链表则程序返回true,不是回文链表则程序返回false)如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的
题解接口:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/ class Solution { public:bool isPalindrome(ListNode* head) {} };
2.问题分析与求解
如果要求题解的时间复杂度为O(N),空间复杂度为O(1),那么本题的求解要分为三个部分:
- 用快慢指针法找到链表中间位置节点
- 将链表后半部分进行反转
- 用双指针法将链表前半部分和后半部分进行比对来判断链表是否回文
(1) 快慢指针法定位链表的中间节点
- 思路是两个指针同时遍历链表,快指针一次走两步(fast=fast->next->next),慢指针一次走一步(slow = slow->next)。
- 当快指针结束遍历时,慢指针恰好会指向中间位置的节点(对于奇数个节点的链表而言,慢指针最后会指向中间节点,对于偶数个节点的链表而言,慢指针最后会指向中间两个节点的第二个节点)
寻找中间位置节点的接口:
ListNode * FindMid(ListNode * head){ListNode* fast = head;ListNode* slow = head;while(fast && fast->next) //注意循环的限制条件{fast = fast->next->next;slow = slow->next;}return slow;}
- 我们以偶数个节点链表的情况为例,简单地证明一下慢指针最后会指向中间两个节点的第二个节点:
对于奇数个节点链表的情况也可以作相似的证明。
(2) 将链表后半部分进行反转
- 定位链表中间位置节点后,我们便可以将链表的后半部分进行反转.
- 完成链表反转的最优方法是三指针反转法(动画):
三指针反转链表
的接口:
ListNode * reverse (ListNode * head){ListNode * cur = (nullptr == head)? nullptr : head->next;ListNode * pre = head;while(cur){ListNode* Next = cur->next;cur->next = pre;pre = cur;cur = Next;}if(head)head->next = nullptr; //记得将被反转部分链表的尾结点的指针域置空return pre; //pre最终指向反转链表的表头}
附:递归法反转链表
递归算法经常出现在单链表问题的题解中,其原因在于:递归算法可以利用多个函数栈帧来存储每一个链表节点的地址(而单链表的缺陷正是在于寻址困难),所以递归算法经常作为单链表问题的可行解之一.(但是递归算法由于压栈开销较大,往往并不是最优解,比如递归法反转链表在时间和空间上的开销都要比三指针反转法更大)
然而以思维训练和加深对递归的理解为目的,这里尝试着解构一下递归反转单链表的算法。
反转单链表递归函数的建立:
- 递归反向遍历链表节点的框架:
ListNode* reverseList (ListNode * head){if(head->next == nullptr)//递归的结束条件{return head;}reverseList(head->next);return head; }
该递归框架可以实现反向遍历单链表(图解)
- 在递归函数反向遍历链表节点的过程中我们可以加入修改节点指针域的操作:
ListNode* reverseList (ListNode * head){if(head->next == nullptr)//递归的结束条件{return head;}reverseList(head->next);head->next->next = head; head->next = nullptr;return head;}
递归函数修改节点指针域过程动画解析:
- 我们希望函数能够将反转后链表的新头节点的地址作为最终返回值带回:
ListNode* reverseList (ListNode * head){if(head->next == nullptr)//递归的结束条件{return head;}ListNode* newhead = reverseList(head->next); //利用newhead将新的头节点地址逐层带回head->next->next = head; head->next = nullptr;return newhead;}
递归函数将新的头节点地址逐层带回的过程图解:
递归反转单链表的接口:
ListNode* reverseList(ListNode* head) {if(nullptr == head || nullptr == head->next)//设置递归的限制条件,构建递归框架{return head;}ListNode * newhead = reverseList(head->next);//newhead是为了将新的头节点地址逐层带回到最外层递归函数作为返回值head->next->next = head;//从原尾结点开始实现反向链接head->next = nullptr;//这里逐层置空是为了最后将新的尾结点指针域置空return newhead; }
由于递归算法开销比较大,所以题解接口中我们采用三指针反转法来完成链表的反转.
(3) 双指针法判断链表是否回文
经过前两个步骤后,链表后半部分完成了反转:
最后在题解接口中用双指针判断链表是否回文即可:
题解代码:
class Solution { public:ListNode * FindMid(ListNode * head) //快慢指针法寻找链表中间位置节点的接口{ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow; //返回链表中间位置节点}ListNode * reverse (ListNode * head) //反转链表的接口(三指针翻转法){ListNode * cur = (nullptr == head)? nullptr : head->next;ListNode * pre = head;while(cur){ListNode* Next = cur->next;cur->next = pre;pre = cur;cur = Next;}if(head) head->next = nullptr; //记得将被反转部分链表的尾结点的指针域置空return pre; //pre最终指向反转链表的表头}bool isPalindrome(ListNode* head) {ListNode* mid = FindMid(head);ListNode * reversehead = reverse(mid);ListNode * tem = reversehead;while(reversehead){if(reversehead->val != head->val){return false;}reversehead = reversehead->next;head = head->next;}reverse(tem); //恢复原链表return true;} };
![]()
二.带头双向循环链表的实现
链表共有8个种类,然而在现实中大多情形下能派上用场的链表只有两种:
- 无头单向非循环链表:实际中无头单向非循环链表常作为其他数据结构的子结
构,如哈希桶、图的邻接表等等- 带头双向循环链表:该种链表结构是由设计C++STL的大神设计出来的,结构优良,使用和实现起来都比较方便(每个节点都有两个指针域,比较耗空间)
每个带头双向循环链表都有一个哨兵头节点,该节点不存储有效数据.
带头双向循环链表的环状示意图:
1.头文件
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h>typedef int LTDataType;typedef struct LTNode {LTDataType val;struct LTNode* pre; //指向前一个节点的指针struct LTNode* next; //指向下一个节点的指针 }LTNode;//各个链表操作接口的声明 LTNode* BuyLTNode(LTDataType x); void ListPrint(LTNode* phead); LTNode* ListInit(); LTNode* ListFind(LTNode* phead, LTDataType x);void ListInsert(LTNode* pos, LTDataType x); void ListErase(LTNode* pos, LTNode* phead); void ListPushFront(LTNode* phead, LTDataType x); void ListPopFront(LTNode* phead); void ListPopBack(LTNode* phead); void ListPushBack(LTNode* phead, LTDataType x); void ListDestory(LTNode* phead);
2.节点内存申请接口和链表初始化接口
节点内存申请接口:
LTNode* BuyLTNode(LTDataType x) //向系统申请链表节点空间的接口 {LTNode* NewNode = (LTNode*)malloc(sizeof(LTNode));if (NULL == NewNode){perror("malloc failed:");exit(-1);}NewNode->next = NULL;NewNode->pre = NULL;NewNode->val = x;return NewNode; }
链表初始化接口:
LTNode* ListInit() //链表初始化接口(链表初始化时创建哨兵节点,接口返回哨兵节点的地址) {LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->pre = phead;return phead; }
无头双向循环链表的初始化就是申请一个哨兵节点:
使用时在主函数中用一个LTNode类型的指针接收该哨兵节点的地址.比如:
int main () {phead = ListInit();// 其他链表操作return 0; }
3.链表的打印和查找接口
无头双向循环链表的遍历过程是从哨兵节点的下一个结点开始到哨兵节点前一个节点结束。
void ListPrint(LTNode* phead) //打印链表接口(注意不要打印哨兵节点中的无效数据) {assert(phead);LTNode* tem = phead->next;while (tem != phead){printf("%d ", tem->val);tem = tem->next;}printf("\n"); } LTNode* ListFind(LTNode* phead, LTDataType x) //根据节点中存储的数据查找某个链表节点 {assert(phead);LTNode* tem = phead->next;while (tem != phead){if (x == tem->val){return tem;}tem = tem->next;}return NULL; }
4.链表的增删接口
- 删除pos地址处节点的接口
![]()
void ListErase(LTNode* pos, LTNode* phead) //删除pos位置的节点 {assert(pos && pos != phead);LTNode* Pre = pos->pre;LTNode* Next = pos->next;Pre->next = Next;Next->pre = Pre;free(pos);pos = NULL; }
- 在pos地址节点的后一个位置插入一个节点的接口:
void ListInsert(LTNode* pos, LTDataType x) //在pos位置后插入一个链表节点的接口 {assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* Next = pos->next;pos->next = newnode;newnode->pre = pos;newnode->next = Next;Next->pre = newnode; }
头插,头删以及尾插尾删接口通过复用上面的两个接口即可实现:
void ListPushFront(LTNode* phead, LTDataType x) //头插一个节点 {assert(phead);ListInsert(phead, x); } void ListPopFront(LTNode* phead) //头删一个节点 {assert(phead && phead->next != phead);ListErase(phead->next, phead); } void ListPopBack(LTNode* phead) //尾删一个节点 {assert(phead && phead->pre != phead);ListErase(phead->pre, phead); } void ListPushBack(LTNode* phead, LTDataType x) //尾插一个节点 {assert(phead);ListInsert(phead->pre, x); }
- 注意哨兵节点不允许在删除数据操作中被删除
5.链表销毁接口
void ListDestory(LTNode* phead) //销毁链表的接口 {assert(phead);LTNode* tem = phead->next;while (tem != phead){LTNode* Next = tem->next;free(tem);tem = Next;}free(phead);phead = NULL; }
注意哨兵节点最后才销毁
可以看见,带头双向循环链表的各个操作接口的时间复杂度都是O(1),这点充分体现了其数据结构的优良性。
相关文章:

数据结构:链表基础OJ练习+带头双向循环链表的实现
目录 一.leetcode剑指 Offer II 027. 回文链表 1.问题描述 2.问题分析与求解 (1) 快慢指针法定位链表的中间节点 (2) 将链表后半部分进行反转 附:递归法反转链表 (3) 双指针法判断链表是否回文 二.带头双向循环链表的实现 1.头文件 2.节点内存申请接口和链表初始化接口…...

计算机视觉方向地理空间遥感图像数据集汇总
文章目录1.DSTL卫星图像数据集/Kaggle竞赛2.Swimming Pool and Car Detection/Kaggle竞赛3.SpaceNet Challenge 3数据集4.RarePlanes数据集5.BigEarthNet数据集6.NWPU VHR-10数据集7.UC Merced Land-Use数据集8.Inria Aerial Image Labeling数据集9.RSOD数据集1.DSTL卫星图像数…...
信息系统项目管理师真题精选(一)
1.信息系统的( )决定了系统可以被外部环境识别,外部环境或者其他系统可以按照预定的方法使用系统的功能或者影响系统的行为。A.可嵌套性B.稳定性C.开放性D.健壮性2、在实际的生产环境中,( )能使底层物理硬件…...
信息系统项目管理师刷题知识点(持续更新)
主要记录自己在备考高项过程中知识点 信息系统项目管理师刷题知识点(按刷题顺序排列) 1.信息技术应用是信息化体系六要素中的龙头,是国家信息化建设的主阵地,集中体现了国家信息化建设的需求和效益。 2.原型化方法也称为快速原型法…...

RabbitMq及其他消息队列
消息队列中间价都有哪些 先进先出 Kafka、Pulsar、RocketMQ、RabbitMQ、NSQ、ActiveMQ Rabbitmq架构 消费推拉模式 客户端消费者获取消息的方式,Kafka和RocketMQ是通过长轮询Pull的方式拉取消息,RabbitMQ、Pulsar、NSQ都是通过Push的方式。 pull类型…...

Toolformer: Language Models Can Teach Themselves to Use Tools
展示了LM可以通过简单的API教自己使用外部工具,并实现两个世界的最佳效果。我们介绍了Toolformer,这是一个经过训练的模型,可以决定调用哪些API,何时调用,传递哪些参数,以及如何将结果最好地纳入未来的标记…...
悲观锁与乐观锁
何谓悲观锁与乐观锁 乐观锁对应于生活中乐观的人总是想着事情往好的方向发展,悲观锁对应于生活中悲观的人总是想着事情往坏的方向发展。这两种人各有优缺点,不能不以场景而定说一种人好于另外一种人。 悲观锁 总是假设最坏的情况,每次去拿数据…...

LeetCode 25. K 个一组翻转链表
原题链接 难度:hard\color{red}{hard}hard 题目描述 给你链表的头节点 headheadhead , kkk 个节点一组进行翻转,请你返回修改后的链表。 kkk 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 kkk 的整数倍…...
朗润国际期货招商:历次科技风头下巨头的博弈
历次科技风头下巨头的博弈 VR/AR、区块链、折叠屏、元宇宙、AIGC五轮科技风头下巨头们都进场了吗? VR/AR硬件 谷歌:2014年入局,推出AR眼镜 百度:未入局 京东:未入局 腾讯:传要开发 亚马逊࿱…...

配置中心Config
引入依赖<parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.0.6.RELEASE</version></parent><properties><spring-cloud.version>Finchley.SR…...

【原创】java+jsp+servlet学生信息管理系统(jdbc+ajax+filter+cookie+分页)
一直想写一个比较基础的JavaWeb项目,然后综合各种技术,方便Java入门者进行学习。学生信息管理系统大家一般接触的比较多,那么就以这个为例来写一个基础项目吧。 需求分析: 使用jspservletmysql开发的学生信息管理系统࿰…...

链表题目总结 -- 回文链表
目录一. 从中心开始找最大的回文字符串1. 思路简述2. 代码3. 总结二. 判断是否为回文字符串1. 思路简述2. 代码3.总结三. 判断是否是回文链表1. 思路简述2. 代码3. 总结4. 优化解法一. 从中心开始找最大的回文字符串 题目链接:没有。给定一个字符串s,从…...
JAVA集合之List >> Arraylist/LinkedList/Vector结构
在Java开发过程中,可能经常会使用到List作为集合来使用,List是一个接口承于Collection的接口,表示着有序的列表。而我们要讨论的是它下面的实现类Arraylist/LinkedList/Vector的数据结构及区别。 ArrayList ArrayList:底层为数组…...

Linux多进程开发
一、进程概述 1、程序和进程 程序是包含一系列信息的文件,这些信息描述了如何在运行时创建一个进程: 二进制格式标识:每个程序文件都包含用于描述可执行文件格式的元信息。内核利用此信息来解释文件中的其他信息。(ELF可执行连…...

三维重建小有基础入门之特征点检测基础
前言:本文将从此篇开始,记录自己从普通CVer入门三维重建的学习过程,可能过程比较坎坷,都在摸索阶段,但争取每次学习都能进一步,提高自己的能力,同时,每篇文章都会按情况相应地推出B站…...

基于node.js+vue+mysql考研辅导学习打卡交流网站系统vscode
语言 node.js 框架:Express 前端:Vue.js 数据库:mysql 数据库工具:Navicat 开发软件:VScode 主要功能包括管理员:首页、个人中心、用户管理、每日打卡管理、考研学校管理、考研专业管理、直通车管理、学习教材管理、…...

【C++、数据结构】封装unordered_map和unordered_set(用哈希桶实现)
文章目录📖 前言1. 复用同一个哈希桶⚡1.1 🌀修改后结点的定义1.2 🌀两个容器各自模板参数类型:2. 改造之后的哈希桶⛳3. 哈希桶的迭代器🔥3.1 💥哈希桶的begin()和 end(…...
StratoVirt 的 vCPU 拓扑(SMP)
CPU 拓扑用来表示 CPU 在硬件层面的组合方式,本文主要讲解 CPU 拓扑中的 SMP(Symmetric Multi-Processor,对称多处理器系统)架构,CPU 拓扑还包括其他信息,比如:cache 等,这些部分会在…...
现在直播大部分都是RTMP RTMP VS RTC
一 RTMP 抓了下抖音直播的包,windows端,走的TCP,加密了,估计还是RTMP。 我以为直播带货,都是RTC了。 快手直播也是TCP,地址用了IPV6。 淘宝直播也是。现在大部分直播都是RTMP。 只有视频会议走的RTC。…...
【Unity实战100例】Unity循环UI界面切换卡片功能
目录 编辑 一:制作UI界面 二:代码逻辑 1.定义基础变量...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...