数据结构算法题(力扣)——链表
以下题目建议大家先自己动手练习,再看题解代码。这里只提供一种做法,可能不是最优解。
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…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
