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

【数据结构】经典链表题目详解集合(反转链表、相交链表、链表的中间节点、回文链表)

文章目录

  • 一、反转链表
    • 1、程序详解
    • 2、代码
  • 二、相交链表
    • 1、程序详解
    • 2、代码
  • 三、链表的中间节点
    • 1、程序详解
    • 2、代码
  • 四、回文链表
    • 1、程序详解
    • 2、代码

一、反转链表

1、程序详解

题目:给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。

示例 :(将链表逆置)
在这里插入图片描述

  1. 方法一:创建新链表。 遍历原链表,并将节点依次头插到新链表中。
  2. 方法二:创建三个指针 。 通过指针的不断移动,依次完成反转
    创建三个结构体指针:n1、n2、n3
    令 n1指向空,n2指向头节点,n3指向头结点的下一个节点
    在这里插入图片描述
    分为两个步骤:
    1、n2->next=n1, 令n2指向n1
    2、n1、n2、n3不断向后移动
    在这里插入图片描述

2、代码

struct ListNode* reverseList(struct ListNode* head){if(head==NULL)return head;struct ListNode* n1, *n2, *n3;n1=NULL, n2=head, n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;
}

二、相交链表

1、程序详解

题目:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
在这里插入图片描述
注:根据一个节点只能有一个next,相交链表一定是Y型的。

当然也有两种方法:(一定要用地址来判断)

  • 方法一:暴力求解,双层循环。
    A链表中的节点依次与B链表中的所有节点相比较,此时,时间复杂度为O(N^2)
  • 方法二:双指针
    1、找出A链表与B链表长度,相减得差值k
    2、让长链表的指针先走k步
    3、A与B的指针同时走,并相比较
    在这里插入图片描述

2、代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode * curA = headA, *curB = headB;int len1 = 1, len2=1;  //用len1,len2来记录两链表的长度,但在循环里面少记录一个,故初始化为1while(curA->next){curA = curA->next;len1++;}while(curB->next){curB = curB->next;len2++;}//若尾节点不相等,则两链表一定不相交if(curA != curB){return NULL;}//相交//找出长链表和短链表struct ListNode * longList = headA, *shortList = headB;int gre = abs(len1-len2);if(len1<len2){longList = headB;shortList = headA;}//找出长短链表后,让长链表先走差步while(gre--){longList = longList->next;}//两链表同时走while(longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;
}

三、链表的中间节点

1、程序详解

题目:给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。
在这里插入图片描述

  • 方法:快慢指针
    若使快指针的速度始终是慢指针的二倍,那么当快指针走到链表结尾,慢指针刚好走到链表的中间。
    在这里插入图片描述

2、代码

struct ListNode* middleNode(struct ListNode* head) {//快慢指针,快指针走两步,慢指针走一步struct ListNode* fast = head, *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

四、回文链表

1、程序详解

题目:给你一个单链表的头节点 head ,请你判断该链表是否为
回文链表。如果是,返回 true ;否则,返回 false 。
在这里插入图片描述

  • 方法:
    1、找到中间节点
    2、将中间节点之后的节点进行反转
    3、将中间节点之前的与反转后的节点 的val值进行比较

故回文链表综合了 反转链表与链表的中间节点,了解了这两个题目方法后,我们只需写进行比较的代码。
在这里插入图片描述

2、代码

//找中间节点
struct ListNode *fac1(struct ListNode * head)
{struct ListNode * fast=head, *slow=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}
//反转
struct ListNode *fac2(struct ListNode * head)
{struct ListNode * n1, *n2, *n3;n1=NULL, n2=head, n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;
}
bool isPalindrome(struct ListNode* head) {struct ListNode * mid = fac1(head);struct ListNode * rmid = fac2(mid);//进行比较while(rmid && head){if(rmid->val != head->val)return false;rmid=rmid->next;head=head->next;}return true;
}

相关文章:

【数据结构】经典链表题目详解集合(反转链表、相交链表、链表的中间节点、回文链表)

文章目录 一、反转链表1、程序详解2、代码 二、相交链表1、程序详解2、代码 三、链表的中间节点1、程序详解2、代码 四、回文链表1、程序详解2、代码 一、反转链表 1、程序详解 题目&#xff1a;给定单链表的头节点 head &#xff0c;请反转链表&#xff0c;并返回反转后的链…...

人工智能在软件开发中的角色:助手还是取代者?

人工智能在软件开发中的角色&#xff1a;助手还是取代者&#xff1f; 随着科技的飞速发展&#xff0c;生成式人工智能&#xff08;AIGC&#xff09;在软件开发领域的应用越来越广泛。从代码生成、错误检测到自动化测试&#xff0c;AI工具正成为开发者的重要助手。然而&#xf…...

qt播放视频

在Qt中播放视频&#xff0c;通常可以使用QMediaPlayer和QVideoWidget这两个类。QMediaPlayer用于控制视频的播放&#xff0c;而QVideoWidget则用于显示视频。 以下是一个简单的示例&#xff0c;展示了如何使用Qt播放视频&#xff1a; cpp复制代码 #include <QApplication…...

搭建论坛和mysql数据库安装和php安装

目录 概念 步骤 安装mysql8.0.30 安装php 安装Discuz 概念 搭建论坛的架构&#xff1a; lnmpDISCUZ l 表示linux操作系统 n 表示nginx前端页面的web服务 m 表示 mysql 数据库 用来保存用户和密码以及论坛的相关内容 p 表示php 动态请求转发的中间件 步骤 &#xff…...

[护网训练]原创应急响应靶机整理集合

前言 目前已经出了很多应急响应靶机了&#xff0c;有意愿的时间&#xff0c;或者正在准备国护的师傅&#xff0c;可以尝试着做一做已知的应急响应靶机。 关于后期&#xff1a; 后期的应急响应会偏向拓扑化&#xff0c;不再是单单一台机器&#xff0c;也会慢慢完善整体制度。…...

【Linux】:程序地址空间

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关Linux程序地址空间的相关知识点&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从…...

c++ 学习面试之路

引用与指针有什么区别&#xff1f; 指针和引用都是地址的概念&#xff0c;指针指向一块内存&#xff0c;它的内容是所指内存的地址&#xff1b;引用是某块内存的别名。 程序为指针变量分配内存区域&#xff0c;而不为引用分配内存区域。 指针使用时要在前加 * &#xff0c;引…...

Linux文件结构

与Windows下的文件组织结构不同&#xff0c;Linux不使用磁盘分区符号来访问文件系统&#xff0c;而是将整个文件系统表示成树状结构&#xff0c;Linux系统每增加一个文件系统都会将其加入到这个树中。 操作系统文件结构的开始只有一个单独的顶级目录结构&#xff0c;叫做根目录…...

【简单介绍下Memcached】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…...

字符串和正则表达式踩坑

// 中石化加油卡号格式&#xff1a;以 100011 开头共19位public static final String ZHONGSHIYOU_OIL_CARD_PATTERN "^100011\\d{13}$";// 中石油加油卡号格式&#xff1a;以90、95、70开头共16位public static final String ZHONGYOU_OIL_CARD_PATTERN "^(9…...

LLM4Decompile——专门用于反编译的大规模语言模型

概述 论文地址&#xff1a;https://arxiv.org/abs/2403.05286 反编译是一种将已编译的机器语言或字节码转换回原始高级编程语言的技术。该技术用于分析软件的内部工作原理&#xff0c;尤其是在没有源代码的情况下&#xff1b;Ghidra 和 IDA Pro 等专用工具已经开发出来&#…...

关于Web开发的详细介绍

目录 一、什么是Web&#xff1f; 二、Web网站的工作流程和开发模式 &#xff08;1&#xff09;简单介绍 &#xff08;2&#xff09;工作流程 1、第一步 2、第二步 &#xff08;3&#xff09;Web网站的开发模式 1、前后端分离开发模式 ​编辑2、混合开发模式 三、开发W…...

G1 垃圾收集器

从 JDK1.9 开始默认 G1&#xff0c;应用在多处理器和大容量内存环境中。 基础概念 Region G1 给整一块Heap内存区域均匀等分了N个 Region&#xff0c;N 默认情况下是 2048。 Region的大小只能是1M、2M、4M、8M、16M或32M (1-32M,并且为2的指数)&#xff0c;比如-Xmx16g -Xms…...

Linux Ubuntu 20.04.06 安装Onboard虚拟键盘教程

目录 一、在线安装 二、源码安装 三、包安装 四、设置 五、禁用系统键盘 一、在线安装 sudo apt-get update #更新软件源 sudo apt-get install onboard #安装Onboard sudo apt-get purge onboard # 卸载 安装后&#xff0c;如果在终端使用命令&#xff1a;onboard 启…...

简介空间复杂度

我们承接上一篇博客。我们写了时间复杂度之后&#xff0c;我们就要来介绍一下另一个相关复杂度了。空间复杂度。我觉得大家应该对空间复杂度认识可能比较少一些。我就是这样&#xff0c;我很少看见题目中有明确要求过空间复杂度的。但确实有这个是我们不可忽视的&#xff0c;所…...

windows server2016搭建AD域服务器

文章目录 一、背景二、搭建AD域服务器步骤三、生成可供java程序使用的keystore文件四、导出某用户的keytab文件五、主机配置hosts文件六、主机确认是否能ping通本人其他相关文章链接 一、背景 亲测可用,之前搜索了很多博客&#xff0c;啥样的都有&#xff0c;就是不介绍报错以…...

android deep links即scheme uri跳转以及googlePlay跳转配置

对于googlePlay的Custom URL就是googlePlay上APP网址&#xff1a; https://play.google.com/store/apps/details?idcom.yourapp如果是国内一些应用&#xff0c;则考虑market://包名等方式&#xff0c;自行百度。 对于Android URI Scheme&#xff1a; 首先需要在Manifest xm…...

QT5.14.2与Mysql8.0.16配置笔记

1、前言 我的QT版本为 qt-opensource-windows-x86-5.14.2。这是QT官方能提供的自带安装包的最近版本&#xff0c;更新的版本需要自己编译源代码&#xff0c;可点击此链接进行下载&#xff1a;Index of /archive/qt/5.14/5.14.2&#xff0c;选择下载 qt-opensource-windows-x86…...

判断是否为完全二叉树

目录 分析 分析 1.完全二叉树的概念&#xff1a;对于深度为K的&#xff0c;有n个结点的二叉树&#xff0c;当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 2.思路&#xff1a;可以采…...

【笔记】记一次redis将从节点变成主节点 主节点变成从节点

1.连上虚拟机centos7 2.打开finalshell连接虚拟机 将从节点变为主节点 输出redis-cli -p 要变成主节点的从节点 -a此从节点的密码 输入 replicaof no one 查看端口状态 info replication 总结&#xff1a; redis-cli -p 端口号 -a 密码 replicaof no one info replicati…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...