“手撕”链表的九道OJ习题
目录
1. 第一题
2. 第二题
3. 第三题
4. 第四题
5. 第五题
6. 第六题
7. 第七题
8. 第八题
9. 第九题
1. 第一题
删除链表中等于给定值 val 的所有节点。OJ链接
思路如下:
相当于链表的removeAll();制定prev和cur,prev记录前一个节点,方便删除。
但是要注意head==null和head.val==val的时候
public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}ListNode cur = head.next;ListNode prev = head;while (cur != null) {if (cur.val == val) {prev.next = cur.next;cur = cur.next;} else {prev = cur;cur = cur.next;}}if (head.val == val) {head = head.next;}return head;}
2. 第二题
反转一个单链表。OJ链接
思路如下:
头插法,把后面的头插到前面
public ListNode reverseList(ListNode head) {if (head == null) {return head;}ListNode cur = head.next;head.next = null;while (cur != null) {ListNode curN = cur.next;cur.next = head;head = cur;cur = curN;}return head;}
3. 第三题
给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。OJ链接
思路如下:
快慢指针,快指针走2步,慢指针走1步,当快指针走完,慢指针刚刚好走一半
public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}
4. 第四题
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ链接
思路如下:
定义一个傀儡头节点和tmp,让headA和headB去比较,如果谁小,tmp就跟在谁的后面,然后head小的++,直到一个链表为空
public ListNode mergeTwoLists(ListNode headA, ListNode headB) {ListNode newH = new ListNode(0);ListNode tmp = newH;while (headA != null && headB != null) {if (headA.val < headB.val) {tmp.next = headA;headA = headA.next;} else {tmp.next = headB;headB = headB.next;}tmp = tmp.next;}if (headA == null) {tmp.next = headB;}if (headB == null) {tmp.next = headA;}return newH.next;}
5. 第五题
写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。OJ链接
思路如下:
两个链表,一个小链表(头节点as,尾节点ae),一个大链表(头节点bs,尾节点be),小于x放小链表,大于x放大链表。然后让ae指向bs,把两个连接起来
public ListNode partition(ListNode pHead, int x) {// write code hereListNode as = null;ListNode ae = null;ListNode bs = null;ListNode be = null;ListNode cur = pHead;while (cur != null) {if (cur.val < x) {if (as == null) {as = ae = cur;} else {ae.next = cur;ae = ae.next;}} else {if (bs == null) {bs = be = cur;} else {be.next = cur;be = be.next;}}cur = cur.next;}if (as == null) {return bs;}ae.next = bs;if (bs != null) {be.next = null;}return as;}
6. 第六题
链表的回文结构。OJ链接
思路如下:
用快慢指针找出中间节点,然后把后面的节点进行头插,最后头和尾开始比较val值相不相同
public boolean chkPalindrome(ListNode A) {// write code hereif (A == null) {return true;}ListNode slow = A;ListNode fast = A;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}ListNode cur = slow.next;while (cur != null) {ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}while (A != slow) {if (A.val != slow.val) {return false;}if (A.next == slow) {return true;}A = A.next;slow = slow.next;}return true;}
7. 第七题
输入两个链表,找出它们的第一个公共结点。OJ链接
思路如下:
两条链表定义p1和p2,求出每条链表的长度,然后相减,得出多出来的距离,把多出来的距离让长的链表先走。然后两个节点一起走,相遇的点就是公共的第一个节点
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 = headA;ListNode p2 = headB;int lenA = 0;int lenB = 0;while (p1 != null) {lenA++;p1 = p1.next;}while (p2 != null) {lenB++;p2 = p2.next;}int len = lenA - lenB;p1 = headA;p2 = headB;if (len < 0) {p1 = headB;p2 = headA;len = lenB - lenA;}while (len != 0) {p1 = p1.next;len--;}while (p1 != p2) {p1 = p1.next;p2 = p2.next;}if (p1 == null) {return null;}return p1;}
8. 第八题
给定一个链表,判断链表中是否有环。OJ链接
思路如下:
快慢指针,快的走两步,慢的走一步。也就是快的先进圈,如果他俩相遇了,就说明有环(假设没环的话,快的先进去,早就空指针null了)
public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {return true;}}return false;}
相遇的原理:
因为fast走得快,slow走得慢。所以fast先进环,slow后进环,我们可以看成fast进了环之后再追slow。我们假设他们距离为N,fast快一步,所以每次都缩短1步,到0之后就相遇了。如下图:
如果fast一次走三步,还能相遇吗?那么他们每走一步追2,如下图:
9. 第九题
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 NULL OJ链接
思路如下:
如果快慢指针,快指针走2步,慢指针走1步,她两相遇了,说明有环,这时候我们让快指针重新出发(fast=head),他和慢指针现在以相同的速度前行,当他们再次相遇的时候,就是出口!
public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {break;}}if (fast == null || fast.next == null) {return null;}fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}
}
相关文章:
“手撕”链表的九道OJ习题
目录 1. 第一题 2. 第二题 3. 第三题 4. 第四题 5. 第五题 6. 第六题 7. 第七题 8. 第八题 9. 第九题 1. 第一题 删除链表中等于给定值 val 的所有节点。OJ链接 思路如下: 相当于链表的removeAll();制定prev和cur,prev记录前一个节点ÿ…...
解决 Git commit 或 Git merge 跑到 VIM 里面去了
像 git commit 分支名字 或 git merge 分支名字这个命令后面最好加上 -m "消息",如果你不加上 -m "消息"的话,它会打开一个程序让你去加上消息,这个程序还是在控制台里面,只不过是 Linux 里面一个叫做 VIM 的…...
营造科技展厅主题氛围,多媒体应用有哪些新策略?
长久以来,展厅作为线下向公众传递信息的窗口,其设计风格与内容主题紧密相连,展现出千姿百态的面貌。然而,随着数字多媒体技术的日新月异,展厅不再仅仅是传统的信息展示平台,而是成为了引领内容展示潮流的风…...
【UML用户指南】-04-从代码到UML的关键抽象
1、关键抽象 声明了一个名为paint的操作,它的实现调用名为drawString的另一个操作,drawString操作负责在指定的位置上打印“Hello,World!”。在通常的面向对象的方式下,drawString是一个名称为g的参数上的一个操作,g的类型是类Gr…...
(2024,LoRA,全量微调,低秩,强正则化,缓解遗忘,多样性)LoRA 学习更少,遗忘更少
LoRA Learns Less and Forgets Less 公和众和号:EDPJ(进 Q 交流群:922230617 或加 VX:CV_EDPJ 进 V 交流群) 目录 0. 摘要 1. 引言 2. 背景 3. 实验设置 3.2 使用编码和数学基准测试来衡量学习(目标域…...
【Java】面向对象的三大特征:封装、继承、多态
封装 什么叫封装? 在我们写代码的时候经常会涉及两种角色: 类的实现者 和 类的调用者。 封装的本质就是让类的调用者不必太多的了解类的实现者是如何实现类的, 只要知道如何使用类就行了,这样就降低了类使用者的学习和使用成本&a…...
请问Java8进阶水平中,常用的设计模式有哪些?
设计模式通常被分为三大类:创建型(Creational)、结构型(Structural)和行为型(Behavioral)。以下是这20个设计模式的分类: 创建型(Creational)设计模式&#…...
力扣--最大子数组和
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 示例 1: 输入:nums [-2,1,-3,4,-1,2,1,-5,4] 输出:…...
C# 中的字符与字符串
简介 在C#编程语言中,字符和字符串是处理文本数据的基础。字符是单个的字母或符号,而字符串是字符的集合。本篇博客将详细介绍C#中的字符类型 char 和字符串类型 string,以及它们的基本操作。 字符类型 char char 类型在C#中用于表示单个字…...
TPM之VMK密封
本篇文章主要介绍基于TPM的Bitlocker全盘加密时,VMK密钥的密封(Seal)流程,至于TPM、Bitlocker、密钥保护器、VMK密钥等这些东西是什么,这里不做解释,需要自己脑补一下(╮(╯▽╰)╭)…...
Fastjson 反序列化漏洞[1.2.24-rce]
漏洞复现环境搭建请参考 http://t.csdnimg.cn/vSaaw kali切换jdk版本请参考 Kali安装JAVA8和切换JDK版本的详细过程_kali安装jdk8-CSDN博客 漏洞原理 Fastjson提供的com.sun.rowset.JdbcRowSetImpl类下的dataSourceName方法支持传入一个RMI/LDAP源,支持远程调用。…...
【面试宝藏】Go基础面试题其一
探索Go语言:特性、用法与最佳实践 Go语言(Golang)自发布以来迅速成为开发者社区中的热门选择。本文将探讨Go语言的优势、数据类型、包管理、类型转换、并发处理、同步机制、通道特性及其使用中的注意事项等内容,并回答一些常见的…...
python如何安装pyqt4
第一步,下载.whl文件,地址:https://www.lfd.uci.edu/~gohlke/pythonlibs/#pyqt4,这里可以下载不同的python版本对应的包。 第二步,选择一个目录,将下载好的文件放到该目录下,然后cmd下ÿ…...
调用上传文件接口出现格式错误
一、造成这种错误的可能有很多 1.检查一下传递格式 2.检查一下接口要求的格式 二、举个例子 这两个有什么区别? 那就是json、和form-data,一定要看仔细接口 如果还是按照json的方式去传就会报错 三、更改header里Content-Type的类型 json等的heade…...
leetcode148. 排序链表,归并法,分治的集大成之作
leetcode148. 排序链表 题目链接 给你链表的头结点 head ,请将其按升序排列并返回排序后的链表。 示例 1: 输入:head [4,2,1,3] 输出:[1,2,3,4] 输入:head [-1,5,3,4,0] 输出:[-1,0,3,4,5] 示例 3&…...
一维时间序列信号的小波模极大值分解与重建(matlab R2018A)
数学上称无限次可导函数是光滑的或没有奇异性,若函数在某处有间断或某阶导数不连续,则称函数在此处有奇异性,该点就是奇异点。奇异性反映了信号的不规则程度,因为信号的奇异点和突变部分往往携带者重要信息,因此信号的…...
五分钟“手撕”栈
实现代码放开头,供大家学习与查阅 目录 一、实现代码 二、什么是栈 三、栈的常见操作 底层实现是链表。 入栈 出栈 四、Stack的使用 五、栈的习题 第一题 第二题 第三题 第四题 第五题 第六题 第七题 六、栈、虚拟机栈、栈帧的区别 目录 一、…...
MAC也能玩转3A大作 Crossover使用指南 crossover运行战地5
众所周知,在Mac上你本不该玩游戏。但是如果你实在犯了这个瘾了,你可以使用Parallel Desktop来运行所有Windows程序。但是繁重的虚拟机对磁盘容量提出了较高的要求,(可能虚拟机用了大概半年就会到60-80GB这样的大小)&am…...
docker私有镜像仓库的搭建及认证
简介: docker私有镜像仓库的搭建及认证 前言 在生产上使用的 Docker 镜像可能包含我们的代码、配置信息等,不想被外部人员获取,只允许内 网的开发人员下载。 Docker 官方提供了一个叫做 registry 的镜像用于搭建本地私有仓库使用。在内部网…...
simCSE句子向量表示(1)-使用transformers API
SimCSE SimCSE: Simple Contrastive Learning of Sentence Embeddings. Gao, T., Yao, X., & Chen, D. (2021). SimCSE: Simple Contrastive Learning of Sentence Embeddings. arXiv preprint arXiv:2104.08821. 1、huggingface官网下载模型 官网手动下载:pri…...
网络运维的重要性
一、介绍 网络运维,英文名为Network Operations (NetOps),指的是负责维护和管理企业或组织内部网络设备和系统的团队或个人。网络运维的主要目标是确保网络的稳定运行和高效性能,以满足企业或组织的需求。 网络运维工作涵盖了多个方面&…...
还不会使用多线程优化代码执行效率?codefun教你在业务场景中使用CompletableFuture进行优化!
业务场景 我们先来从场景入手,具体的业务是这样的:我们需要从某的省的id去查询这个省份所有的县区,至于什么是县区呢?在DB中我们是这样定义的,也就是字段level 3 的时候,就代表一个县的信息,然后呢&#…...
数据结构-堆(带图)详解
前言 本篇博客我们来仔细说一下二叉树顺序存储的堆的结构,我们来看看堆到底如何实现,以及所谓的堆排序到底是什么 💓 个人主页:普通young man-CSDN博客 ⏩ 文章专栏:数据结构_普通young man的博客-CSDN博客 若有问题 评…...
React Native 之 react-native-share(分享)库 (二十三)
react-native-share 是一个流行的 React Native库,它允许你在移动应用中分享文本、链接、图片等内容到各种社交网络和消息应用。以下是对其原理的简要概述以及代码示例的解析。 代码示例解析 1. 安装 npm install react-native-share # 或者 yarn add react-n…...
JCR一区级 | Matlab实现TCN-BiGRU-MATT时间卷积双向门控循环单元多特征分类预测
JCR一区级 | Matlab实现TCN-BiGRU-MATT时间卷积双向门控循环单元多特征分类预测 目录 JCR一区级 | Matlab实现TCN-BiGRU-MATT时间卷积双向门控循环单元多特征分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.Matlab实现TCN-BiGRU-MATT时间卷积双向门控循环单元多…...
游戏心理学Day01
心理学 心理学是一门研究心理过程和行为及其如何受有机体的生理,心理状态和外部影响的科学 心理学不是常识的代名词,心理学分为基础,心理学和应用心理学基础,心理学研究的目的在于描述,解释,预测和控制行…...
错误模块路径: ...\v4.0.30319\clr.dll,v4.0.30319 .NET 运行时中出现内部错误,进程终止,退出代码为 80131506。
全网唯一解决此BUG的文章!!! 你是否碰到了以下几种问题?先说原因解决思路具体操作1、首先将你C:\Windows\Microsoft.NET\文件夹的所有者修改为你当前用户,我的是administrator。2、修改当前用户权限。3、重启电脑4、删…...
005 CentOS 7.9 RabbitMQ安装及配置
https://github.com/rabbitmq/rabbitmq-server/releases https://www.rabbitmq.com/docs/download https://packagecloud.io/rabbitmq/rabbitmq-server https://www.erlang-solutions.com/downloads/ https://www.erlang.org/ 文章目录 卸载erlerl版本安装与下载版本不匹配正…...
Xcode 15 libarclite 缺失问题
升级到Xcode 15运行项目报错,报错信息如下: SDK does not contain libarclite at the path /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/arc/libarclite_iphonesimulator.a; try increasing the minimum d…...
绘画智能体分享
这是您请求的故宫雪景图,角落有一只可爱的胖猫,采用了水墨画风格,类似于张大千的作品。希望您喜欢这幅画! 🎨 选项 1【转变风格】——将这幅画转变为梵高的后印象派风格,增添一些梵高特有的笔触和色彩。 &…...
7_2、C++程序设计进阶:数据共享
数据与函数 数据与函数局部变量全局变量类的数据成员 类的静态成员静态数据成员静态函数成员 友元友元函数友元类 函数之间实现数据共享有以下几种方式:局部变量、全局变量、类的数据成员、类的静态成员和友元。 如何共享局部变量呢? 在主调函数和被调…...
d2-crud-plus 使用小技巧(五)—— 搜索时间(或下拉列表)后,点击X清除按钮后返回值为null,导致异常
问题 使用vue2elementUId2-crud-plus,时间组件自动清除按钮,点击清除按钮后对应的值被设置为null,原本应该是空数组([]),导致数据传到后端后报错。不仅适用于搜索,表单一样有效果。 解决方法 …...
ChatGPT成知名度最高生成式AI产品,使用频率却不高
5月29日,牛津大学、路透社新闻研究所联合发布了一份生成式AI(AIGC)调查报告。 在今年3月28日—4月30日对美国、英国、法国、日本、丹麦和阿根廷的大约12,217人进行了调查,深度调研他们对生成式AI产品的应用情况。 结果显示&…...
R19 NR移动性增强概况
随着5G/5G-A技术不断发展和业务需求的持续增强,未来网络的部署将不断向高频演进。高频小区的覆盖范围小,用户将面临更为频繁的小区选择、重选、切换等移动性过程。 为了提升网络移动性能和保障用户体验,移动性增强一直是3GPP的热点课题。从NR…...
C语言:如何写文档注释、内嵌注释、行块注释?
技术答疑流程 扫描二维码,添加个人微信;支付一半费用,获取答案;如果满意,则支付另一半费用; 知识点费用:10元 项目费用:如果有项目任务外包需求,可以微信私聊...
Turtle中circle用法详解
在Python的Turtle图形库中,circle方法是一个非常灵活的工具,它允许我们以简单的方式绘制圆或圆的一部分。本文将深入探讨circle方法,特别关注radius和extent参数的用途及其正负值的意义。 一、circle方法概览 首先,让我们了解一…...
stack和queue(1)
一、stack的简单介绍和使用 1.1 stack的介绍 1.stack是一种容器适配器,专门用在具有先进后出,后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入和弹出操作。 2.stack是作为容器适配器被实现的,容器适配器即是…...
前端3剑客(第1篇)-初识HTML
100编程书屋_孔夫子旧书网 当今主流的技术中,可以分为前端和后端两个门类。 前端:简单的理解就是和用户打交道 后端:主要用于组织数据 而前端就Web开发方向来说, 分为三门语言, HTML、CSS、JavaScript 语言作用HT…...
植被变化趋势线性回归以及可视化
目录 植被变化线性回归ee.Reducer.linearFit().reduce()案例:天水市2004-2023年EVI线性回归趋势在该图中,使用了从红色到蓝色的渐变来表示负趋势到正趋势。红色代表在某段时间中,植被覆盖减少,绿色表示持平,蓝色表示植被覆盖增加。 植被变化线性回归 该部分参考Google…...
大话设计模式学习笔记
目录 工厂模式策略模式备忘录模式(快照模式)代理模式单例模式迭代器模式访问者模式观察者模式解释器模式命令模式模板方法模式桥接模式适配器模式外观模式享元模式原型模式责任链模式中介者模式装饰模式状态模式 工厂模式 策略模式 核心:封装…...
MiniMax公司介绍
MiniMax是一家专注于通用人工智能技术的科技公司,成立于2021年12月。公司致力于成为通用人工智能时代基础设施建设者和内容应用创造者,积极投身于中国人工智能技术高速发展的时代大潮。MiniMax的团队由多位在人工智能领域有着丰富经验的专家组成…...
lucene 9.10向量检索基本用法
Lucene 9.10 中的 KnnFloatVectorQuery 是用来执行最近邻(k-Nearest Neighbors,kNN)搜索的查询类,它可以在一个字段中搜索与目标向量最相似的k个向量。以下是 KnnFloatVectorQuery 的基本用法和代码示例。 1. 索引向量字段 首先…...
【2023百度之星初赛】跑步,夏日漫步,糖果促销,第五维度,公园,新材料,星际航行,蛋糕划分
目录 题目:跑步 思路: 题目:夏日漫步 思路: 题目:糖果促销 思路: 题目:第五维度 思路: 题目:公园 思路: 新材料 思路: 星际航行 思路…...
vs2019 QT UI 添加新成员或者控件代码不提示问题解决方法
右键点击头文件,添加ui的头文件 添加现有项 找到uic目录的头文件 打开ui,QtWidgetsApplication2.ui,进行测试 修改一个名字: 重点: 设置一个布局: 点击生成解决方案: 以后每次添加控件后,记得点击保存 这样…...
【面试八股总结】MySQL事务:事务特性、事务并行、事务的隔离级别
参考资料:小林coding 一、事务的特性ACID 原子性(Atomicity) 一个事务是一个不可分割的工作单位,事务中的所有操作,要么全部完成,要么全部不完成,不会结束在中间某个环节。原子性是通过 undo …...
STL用法总结
文章目录 vector构造常用函数遍历适用情形注意事项使用迭代器删除可能会出现的错误 Set & MultiSet(不能用sort,会自动排序)构造常用函数删除,查找遍历 unordered_set(不排序集合),unordered_multiset Map & M…...
他人项目二次开发——慎接
接了一个朋友的项目——开发及运营迭代差不多2年多了,整体样子移动端和PC都能正常使用,但后期的扩展性及新功能添加出现瓶颈。 因此给了一部分钱,让我接手来开发——重构架构。 背景说明 朋友公司的技术人员是我帮忙招聘的,相关技…...
k8s之PV、PVC
文章目录 k8s之PV、PVC一、存储卷1、存储卷定义2、存储卷的作用2.1 数据持久化2.2 数据共享2.3 解耦2.4 灵活性 3、存储卷的分类3.1 emptyDir存储卷3.1.1 定义3.1.2 特点3.1.3 用途3.1.4 示例 3.2 hostPath存储卷3.2.1 定义3.2.2 特点3.2.3 用途3.2.4 示例 3.3 NFS存储卷3.3.1 …...
新人学习笔记之(JavaScript作用域)
一、作用域 1.通常来说,一段程序代码中所用的名字并不总是有效和可用的,而限定这个名字的可用性的代码范围就是这个名字的作用域。作用域的使用提高了程序逻辑的局部性,增强了程序的可靠性,减少了名字冲突 二、变量的作用域 1.变…...
图论第一天
在单位摸鱼,地铁上看了个开始,图论开了个头,后面也希望能往这个方向上转,努努力吧。 一周没做题啦,后面坚持继续做题+二刷,接着记录每一天!!!加油࿰…...