数据结构算法题(力扣)——链表
以下题目建议大家先自己动手练习,再看题解代码。这里只提供一种做法,可能不是最优解。
1. 移除链表元素(OJ链接)
题目描述:给一个链表的头节点 head 和一个整数 val ,删除链表中所有满足值等于 val 的节点,并返回新的头节点 。
解法:遍历链表,依次比对结点的值和val是否相等,相等则删除,不相等则更新指针指向,继续遍历。
这里需要分两种情况来讨论,一是链表结点的值都等于val,二是链表结点的值不都等于val。
struct ListNode* removeElements(struct ListNode* head, int val)
{//全部结点的值都等于val或前面部分结点相等while(head&&head->val==val){head=head->next;}//删除全部结点后head为空或者链表本身就为空链表if(!head){return NULL;}struct ListNode* cur=head;while(cur->next){//cur的下一个结点值等于val,则删除下一个if(cur->next->val==val){cur->next=cur->next->next;}//不相等则cur后移一步else{cur=cur->next;}}return head;
}
无论链表结点中是什么样的值,当进行完第一个while循环后,如果head不是NULL,那么我们定义的cur指针指向的结点的值一定不等于val。因此第二个while循环里if的判断条件为cur->next->val==val,这样不需要保留cur的前一个结点,因为cur本身就是前一个结点(可能删除的结点的前一个结点)。
2. 反转链表(OJ链接)
题目描述:给定单链表的头节点 head ,反转链表,并返回反转后的链表的头节点。
我们所要做的操作如下图
如果链表为NULL,直接返回空即可。链表不为空,则需要反转。
以上图链表为例本题解法如下图所示。
当n2为空时,循环结束。
题解代码如下
struct ListNode* reverseList(struct ListNode* head)
{if(head==NULL){return NULL;}struct ListNode* prev=NULL;struct ListNode* cur=head;struct ListNode* next=head->next;while(cur!=NULL){cur->next=prev;prev=cur;cur=next;if(next){next=next->next;}}return prev;
}
注意题解中的prev,cur和next指针分别对应图中的n1,n2,n3。最后一步时n3为NULL,所以需要加判断语句。
3. 链表的中间结点(OJ链接)
题目描述:给定单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
如果链表结点个数为奇数,返回中间结点,如果结点数为偶数,返回第二个结点。比如有六个结点,则返回第四个结点。
解法:快慢指针法。指的是一个指针走的步数多,一个指针走的步数少。此题快指针走两步,慢指针走一步。当快指针走到NULL或最后一个结点时(链表结点数为偶数或奇数),慢指针指向的结点即为中间结点。
题解代码如下
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast=head,*slow=head;while (fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;}return slow;
}
4. 合并两个有序链表(OJ链接)
题目描述:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解法:创建两个指针变量分别指向两个链表的头,依次比较结点的值,值小的结点链接到新链表的尾,依次遍历链表,其中一个链表走完后,将剩余的链表链接到新链表的尾即可。
示例:
题解代码如下
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (!list1) {return list2;}if (!list2) {return list1;}//分别指向两个链表的头结点ListNode *p1 = list1, *p2 = list2;//phead为新链表的头,ptail为新链表的尾ListNode *phead = NULL, *ptail = NULL;//两个链表都没有遍历完while (p1 && p2) {if (p1->val < p2->val) {//链接的是第一个结点if (phead == NULL) {phead = ptail = p1;p1 = p1->next;} else {ptail->next = p1;ptail = ptail->next;p1 = p1->next;}} else {//链接的是第一个结点if (phead == NULL) {phead = ptail = p2;p2 = p2->next;} else {ptail->next = p2;p2 = p2->next;ptail = ptail->next;}}}//链表1没有走完if (p1) {ptail->next = p1;}//链表2没有走完if (p2) {ptail->next = p2;}return phead;
}
5. 返回倒数第k个结点(OJ链接)
题目描述:给定一个单链表的头结点(head),找出单向链表中倒数第 k 个节点。返回该节点的值。
此题和第三题类似。解法依旧是快慢指针法。
解法:快指针先走k步,然后和慢指针一起走,快指针走到NULL时,慢指针指向的结点就是倒数第k个结点。
原理:快指针先走k步,使得两个指针间隔为k。再一起以相同速度走,最后两个指针间隔依旧是k。
题解代码如下
int kthToLast(struct ListNode* head, int k)
{struct ListNode* fast=head,*slow=head;while(k--){fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow->val;
}
这里就先介绍这五个题的做法,大家可以试试用别的做法看是否可以做出来噢。
相关文章:
数据结构算法题(力扣)——链表
以下题目建议大家先自己动手练习,再看题解代码。这里只提供一种做法,可能不是最优解。 1. 移除链表元素(OJ链接) 题目描述:给一个链表的头节点 head 和一个整数 val ,删除链表中所有满足值等于 val 的节点…...
LeetCode---391周赛
题目列表 3099. 哈沙德数 3100. 换水问题 II 3101. 交替子数组计数 3102. 最小化曼哈顿距离 一、哈沙德数 简单的模拟题,代码如下 class Solution { public:int sumOfTheDigitsOfHarshadNumber(int x) {int s 0, tmp x;while(tmp){stmp%10;tmp/10;}return x…...
微信小程序的页面交互2
一、自定义属性 (1)定义: 微信小程序中的自定义属性实际上是由data-前缀加上一个自定义属性名组成。 (2)如何获取自定义属性的值? 用到target或currentTarget对象的dataset属性可以获取数据 ÿ…...
【VSCode】修改插件地址
不想放在原始C盘下面C:\Users\{用户}\.vscode\extensions为了后续存储空间考虑,想通过添加环境变量创建名为VSCODE_EXTENSIONS的环境变量,内容指向vs Code扩展所在目录即可 直接配置环境变量,不要在有空格的文件夹下面 变量名称:…...
自然语言处理NLP概述
大家好,自然语言处理(NLP)是计算机科学领域与人工智能领域中的一个重要方向,其研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法。本文将从自然语言处理的本质、原理和应用三个方面,对其进行概述。 一、NLP的本质 NLP是一种…...
计算机网络——37认证
认证 目标:Bob需要Alice证明他的身份 Protocol ap1.0:Alice说"A am Alice" 可能出现的问题: 在网络上Bob看不到Alice,因此Trudy可以简单的声称他是Alice 认证:重新尝试 Protocol ap2.0:Alice…...
Java中利用BitMap位图实现海量级数据去重
🏷️个人主页:牵着猫散步的鼠鼠 🏷️系列专栏:Java全栈-专栏 🏷️个人学习笔记,若有缺误,欢迎评论区指正 目录 前言 什么是BitMap?有什么用? 基本概念 位图的优势 …...
Linux知识点记录
Linux知识点记录 1. 后台运行应用程序方法一:&方法二:nohup & 2. 一个shell脚本中执行多个应用程序3. 2>&14. shell脚本清除日志5. 通过grep查找匹配字符串 1. 后台运行应用程序 参考文章:https://blog.csdn.net/Pan_peter/…...
js的check函数
在JavaScript中,并没有一个内置的名为check的函数。然而,你可以根据需求自定义一个check函数,用于执行各种验证和检查任务。这个check函数的具体作用完全取决于你如何定义和实现它。 以下是一个简单的示例,展示了如何定义一个che…...
赛尼格磁电科技邀您到场参观2024第13届生物发酵展
参展企业介绍 北京赛尼格磁电科技有限公司是一家中加合资的专业永磁组件生产商,2001年成立于中国北京。公司专业从事磁性材料的应用及各类磁系统的设计、开发及制造,公司产品广泛应用于汽车行业、建筑行业、电子行业、航海领域、医学领域、教育领域等。 …...
gpt国内怎么用?最新版本来了
claude 3 opus面世后,这几天已经有许多应用,而其精确以及从不偷懒(截止到2024年3月11日还没有偷懒)的个性,也使得我们可以用它来首次完成各种需要多轮对话的尝试。 今天我们想要进行的一项尝试就是—— 如何从一个不知…...
Vim脚本语言入门:打造你的编辑器
简介 Vim脚本语言是Vim编辑器内置的一种脚本语言,它赋予用户高度的定制和自动化编辑任务的能力。通过编写Vim脚本,用户可以根据自己的需求来扩展和改进Vim编辑器的功能,从而提高编辑效率和舒适度。 在Vim中,脚本语言被广泛用于创…...
myweb项目资料集
项目要求 前后端分离后端采用 flask 框架前端采用 vue3 框架 后端部分 Flask 3 框架: https://dormousehole.readthedocs.io/en/latest/quickstart.html Session: https://blog.csdn.net/zhangvalue/article/details/93892241 MySQL 操作…...
Kubernetes(k8s):部署、使用 metrics-server
Kubernetes(k8s):部署、使用 metrics-server 一、metrics-server简介二、部署metrics-server2.1、 下载 Metrics Server 部署文件2.2、修改metrics-server.yaml 文件2.3、 部署 Metrics Server2.4、 检查 Metrics Server 三、使用 Metrics Se…...
为什么建议你学习Spring底层原理?
1.根因 Java诞生以来,一直是业界的主流语言和平台,而Spring则是Java开发的平台。与其说是用Java编程,不如说是在Spring框架上编程。即便最近几年比较火的Spring Boot、Spring Cloud,其底层内核仍然是Spring。因此,作为…...
post请求搜索功能爬虫
<!--爬虫仅支持1.8版本的jdk--> <!-- 爬虫需要的依赖--> <dependency> <groupId>org.apache.httpcomponents</groupId> <artifactId>httpclient</artifactId> <version>4.5.2</version> </dependency>…...
#pragma once的作用
使用visual studio新建头文件时,第一行会出现如下默认代码, #pragma once 它是一种编译器指令,通常用于确保头文件只被包含一次,以避免产生重复定义的问题。当编译器处理一个源文件时,遇到#pragma once指令时…...
【Android】图解View的工作流程原理
文章目录 入口DecorView如何加载到Window中MeasureSpec MeasureView的测量ViewGroup的测量 LayoutView的layout() Draw1、绘制背景3、绘制View内容4、绘制子View6、绘制装饰 入口 DecorView如何加载到Window中 MeasureSpec 该类是View的内部类,封装View的规格尺寸…...
记工时流程
记工时流程 加入团体 加入观古鉴古服务队 登录成功后,点击我的-我的成员 添加成员 进入小程序 扫描后登录,我的-我的团体,可以看到观古鉴古服务队, 进入后点项目 选择观古鉴古文化志愿者招募 -> 我要报名 -> 选择文化志…...
Ubuntu20.04使用Neo4j导入CSV数据可视化知识图谱
1.安装JDK( Ubuntu20.04 JDK11) sudo apt-get install openjdk-11-jdk -y java -version which java ls -l /usr/bin/java ls -l /etc/alternatives/java ls -l /usr/lib/jvm/java-11-openjdk-amd64/bin/java确认安装路径为/usr/lib/jvm/java-11-openjd…...
vue-cli打包 nodejs内存溢出 vue2.x Last few GCs
遇到这种情况百度各种博客,什么改package.json里的配置,什么安装increase-memory-limit ,都尝试了并没什么用处,最后解决方案为执行下方名单,再次打包就成功了: export NODE_OPTIONS--max_old_space_size4…...
SpringBoot整合Flowable/Activiti
SpringBoot版本: 2.0.1.RELEASE Flowable版本: 6.3.1 Activiti版本: 6.0.0 一.添加pom依赖 因为之前我整合的时候有报错关于sqlsession的错误,后面查询文章才发现flowable要排除掉mybatis,又没说具体排除哪一个,所以我这干脆全部排除了 <!-- Flowable dependencies -->…...
基础总结篇:Activity生命周期
private int param 1; //Activity创建时被调用 Override public void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); Log.i(TAG, “onCreate called.”); setContentView(R.layout.lifecycle); Button btn (Button) findViewById(R.id.…...
【鸿蒙 HarmonyOS】@ohos.promptAction (弹窗)
一、背景 创建并显示文本提示框、对话框和操作菜单。 文档地址👉:文档中心 说明 本模块首批接口从API version 9开始支持。后续版本的新增接口,采用上角标单独标记接口的起始版本。 该模块不支持在UIAbility的文件声明处使用,即…...
ElasticSearch的常用数据类型
常见的数据类型 Text类型(文本数据类型) 用于全文检索的字段,例如电子邮件的正文或产品的描述。这些字段是analyzed,也就是说,它们通过分析器传递,以便 在被索引之前将字符串转换为单个术语的列表。通过分…...
C/C++预处理过程
目录 前言: 1. 预定义符号 2. #define定义常量 3. #define定义宏 4. 带有副作用的宏参数 5. 宏替换的规则 6. 宏和函数的对比 7. #和## 8. 命名约定 9. #undef 10. 命令行定义 11. 条件编译 12. 头文件的包含 13. 其他预处理指令 总结&#x…...
客服电话系统:专业、便捷的服务沟通桥梁
一、引言 1.客服电话系统在现代服务中的重要性 在信息化时代,服务行业的竞争日益激烈,提供高效、便捷的服务成为企业赢得市场、获取用户信任的关键。客服电话系统作为企业与用户之间的重要沟通桥梁,不仅承载着解答疑问、处理问题的职责&…...
IP地址与子网掩码
1 IP地址 1.1 IPv4与IPv6 1.2 IPv4地址详解 IPv4地址分4段,每段8位,共32位二进制数组成。 1.2.1 地址分类 这32位又被分为网络号和主机号两部分,根据网络号占用位数的不同,又可分为以下几类: A类地址:…...
Python爬取公众号封面图(零基础也能看懂)
📚博客主页:knighthood2001 ✨公众号:认知up吧 (目前正在带领大家一起提升认知,感兴趣可以来围观一下) 🎃知识星球:【认知up吧|成长|副业】介绍 ❤️感谢大家点赞👍&…...
2024.4.6学习笔记
今日学习韩顺平java0200_韩顺平Java_对象机制练习_哔哩哔哩_bilibili 今日学习p315-p328 动态绑定机制 当调用方法对象的时候,该方法会和该对象的内存地址/运行类型绑定 当调用对象属性时,没有动态绑定机制,哪里声明,哪里使用 …...
如何构建自己的网站/最新战争新闻事件今天
一:概述 PC机自从诞生以来,硬件经历了无数变化,CPU从最初的INTEL 8086到现在PIII满大街都是也只不过十几年。微软的WINDOWS操作系统从最初的1.0版本到现在即将推出WIN2000,一直是桌面系统上装机量最大的OS。 作为软件开发人员&am…...
怎么做盗文网站/营销推广的特点
开课时间2019年12月7-8日(周六、周日)(9:00-12:00,13:30-17:30)上课地点成都,人民公园费用每人2400元,含午餐。交通、住宿费请自理。可以开增值税专用发票和增值税普通发票。训练介绍软件开发中,需求是解决“产品怎样好卖”的问题…...
河源哪有做网站/seo排名优化推广
路由器的工作原理 路由表的形成 静态路由和默认路由 路由器转发数据包的封装过程 静态路由和默认路由的配置 路由: 从源路由到目标路由的转发过程 根据路由转发数据 路由表的形成 路由表 路由器中维护的路由条目的集合路由器根据路由表做路径选择路由表的形成…...
做系统用哪个网站好/安卓手机游戏优化器
如果出现死链,请大家及时反映。谢谢:) [colorRed]MSSL宣传片(来自tudou.com)[/color][urlhttp://www.tudou.com/v/KOh50V8RWQI]点击观看[/url] [colorRed]MSSL中文入门视频(来自silverlight.cn)[/color][urlhttp://www.silverlight.cn/techmv/grandpiano_chinese.av…...
新的南宁网站建设公司/代理广告投放平台
点击上方“Java之间”,选择“置顶或者星标”你关注的就是我关心的!作者:Apocalypsa一、简介毕业答辩搞定,总算可以闲一段时间,把这段求职经历写出来,也作为之前三个半月的求职的回顾。首先说说我拿到的offe…...
鸡泽网站建设案例/网站流量统计系统
对于Oracle数据库操作主要使用的是命令行方式,而所有的命令都使用sqlplus完成,对于sqlplus有两种形式。 一种是dos风格的sqlplus:sqlplus.exe;另一种是windows风格的sqlplus:sqlplusw.exe;在Oracle 10g之中主要使用的是sqlplusw命…...