当前位置: 首页 > news >正文

数据结构:链表基础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. 用快慢指针法找到链表中间位置节点
  2. 将链表后半部分进行反转
  3. 用双指针法将链表前半部分和后半部分进行比对来判断链表是否回文

(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个种类,然而在现实中大多情形下能派上用场的链表只有两种:

  1. 无头单向非循环链表:实际中无头单向非循环链表常作为其他数据结构的子结
    ,如哈希桶、图的邻接表等等

  2. 带头双向循环链表:该种链表结构是由设计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.信息系统的&#xff08; &#xff09;决定了系统可以被外部环境识别&#xff0c;外部环境或者其他系统可以按照预定的方法使用系统的功能或者影响系统的行为。A.可嵌套性B.稳定性C.开放性D.健壮性2、在实际的生产环境中&#xff0c;&#xff08; &#xff09;能使底层物理硬件…...

信息系统项目管理师刷题知识点(持续更新)

主要记录自己在备考高项过程中知识点 信息系统项目管理师刷题知识点&#xff08;按刷题顺序排列&#xff09; 1.信息技术应用是信息化体系六要素中的龙头&#xff0c;是国家信息化建设的主阵地&#xff0c;集中体现了国家信息化建设的需求和效益。 2.原型化方法也称为快速原型法…...

RabbitMq及其他消息队列

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

Toolformer: Language Models Can Teach Themselves to Use Tools

展示了LM可以通过简单的API教自己使用外部工具&#xff0c;并实现两个世界的最佳效果。我们介绍了Toolformer&#xff0c;这是一个经过训练的模型&#xff0c;可以决定调用哪些API&#xff0c;何时调用&#xff0c;传递哪些参数&#xff0c;以及如何将结果最好地纳入未来的标记…...

悲观锁与乐观锁

何谓悲观锁与乐观锁 乐观锁对应于生活中乐观的人总是想着事情往好的方向发展&#xff0c;悲观锁对应于生活中悲观的人总是想着事情往坏的方向发展。这两种人各有优缺点&#xff0c;不能不以场景而定说一种人好于另外一种人。 悲观锁 总是假设最坏的情况&#xff0c;每次去拿数据…...

LeetCode 25. K 个一组翻转链表

原题链接 难度&#xff1a;hard\color{red}{hard}hard 题目描述 给你链表的头节点 headheadhead &#xff0c; kkk 个节点一组进行翻转&#xff0c;请你返回修改后的链表。 kkk 是一个正整数&#xff0c;它的值小于或等于链表的长度。如果节点总数不是 kkk 的整数倍&#xf…...

朗润国际期货招商:历次科技风头下巨头的博弈

历次科技风头下巨头的博弈 VR/AR、区块链、折叠屏、元宇宙、AIGC五轮科技风头下巨头们都进场了吗&#xff1f; VR/AR硬件 谷歌&#xff1a;2014年入局&#xff0c;推出AR眼镜 百度&#xff1a;未入局 京东&#xff1a;未入局 腾讯&#xff1a;传要开发 亚马逊&#xff1…...

配置中心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项目&#xff0c;然后综合各种技术&#xff0c;方便Java入门者进行学习。学生信息管理系统大家一般接触的比较多&#xff0c;那么就以这个为例来写一个基础项目吧。 需求分析&#xff1a; 使用jspservletmysql开发的学生信息管理系统&#xff0…...

链表题目总结 -- 回文链表

目录一. 从中心开始找最大的回文字符串1. 思路简述2. 代码3. 总结二. 判断是否为回文字符串1. 思路简述2. 代码3.总结三. 判断是否是回文链表1. 思路简述2. 代码3. 总结4. 优化解法一. 从中心开始找最大的回文字符串 题目链接&#xff1a;没有。给定一个字符串s&#xff0c;从…...

JAVA集合之List >> Arraylist/LinkedList/Vector结构

在Java开发过程中&#xff0c;可能经常会使用到List作为集合来使用&#xff0c;List是一个接口承于Collection的接口&#xff0c;表示着有序的列表。而我们要讨论的是它下面的实现类Arraylist/LinkedList/Vector的数据结构及区别。 ArrayList ArrayList&#xff1a;底层为数组…...

Linux多进程开发

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

三维重建小有基础入门之特征点检测基础

前言&#xff1a;本文将从此篇开始&#xff0c;记录自己从普通CVer入门三维重建的学习过程&#xff0c;可能过程比较坎坷&#xff0c;都在摸索阶段&#xff0c;但争取每次学习都能进一步&#xff0c;提高自己的能力&#xff0c;同时&#xff0c;每篇文章都会按情况相应地推出B站…...

基于node.js+vue+mysql考研辅导学习打卡交流网站系统vscode

语言 node.js 框架&#xff1a;Express 前端:Vue.js 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat 开发软件&#xff1a;VScode 主要功能包括管理员&#xff1a;首页、个人中心、用户管理、每日打卡管理、考研学校管理、考研专业管理、直通车管理、学习教材管理、…...

【C++、数据结构】封装unordered_map和unordered_set(用哈希桶实现)

文章目录&#x1f4d6; 前言1. 复用同一个哈希桶⚡1.1 &#x1f300;修改后结点的定义1.2 &#x1f300;两个容器各自模板参数类型&#xff1a;2. 改造之后的哈希桶⛳3. 哈希桶的迭代器&#x1f525;3.1 &#x1f4a5;哈希桶的begin&#xff08;&#xff09;和 end&#xff08;…...

StratoVirt 的 vCPU 拓扑(SMP)

CPU 拓扑用来表示 CPU 在硬件层面的组合方式&#xff0c;本文主要讲解 CPU 拓扑中的 SMP&#xff08;Symmetric Multi-Processor&#xff0c;对称多处理器系统&#xff09;架构&#xff0c;CPU 拓扑还包括其他信息&#xff0c;比如&#xff1a;cache 等&#xff0c;这些部分会在…...

现在直播大部分都是RTMP RTMP VS RTC

一 RTMP 抓了下抖音直播的包&#xff0c;windows端&#xff0c;走的TCP&#xff0c;加密了&#xff0c;估计还是RTMP。 我以为直播带货&#xff0c;都是RTC了。 快手直播也是TCP&#xff0c;地址用了IPV6。 淘宝直播也是。现在大部分直播都是RTMP。 只有视频会议走的RTC。…...

【Unity实战100例】Unity循环UI界面切换卡片功能

目录 ​编辑 一:制作UI界面 二:代码逻辑 1.定义基础变量...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...