数据结构:链表基础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.定义基础变量...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...