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

【leetcode】链表(2)

目录

1. 环形链表

解题思路

2. 环形链表 II

解题思路

3. 删除排序链表中的重复元素

解题思路

4. 删除排序链表中的重复元素 II

解题思路

5. 移除链表元素

解题思路

6. 链表的中间结点

解题思路


1. 环形链表

OJ:环形链表

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

示例 1:

输入:head = [3,2,0,-4], pos = 1

输出:true

解释:链表中有一个环,其尾部连接到第二个节点。

解题思路

快慢指针

快指针走两步,慢指针走一步,如果链表带环,两个最终肯定会在环内相遇;如果链表不带环,快指针肯定会走到链表的末尾

 public boolean hasCycle(ListNode head) {if(head == null || head.next == null){return false;}ListNode low = head;ListNode fast = head;while(fast != null && fast.next != null){fast = fast.next.next;low = low.next;if(fast == low){return true;}}return false;}

2. 环形链表 II

OJ:环形链表 II

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1

输出:返回索引为 1 的链表节点

解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0

输出:返回索引为 0 的链表节点

解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1

输出:返回 null

解释:链表中没有环。

解题思路

 

public ListNode detectCycle(ListNode head) {
//        快慢指针相遇时,引入新节点从链表头开始,慢的一定会和新节点在环形第一个节点相遇ListNode low = head;ListNode fast = head;while (fast != null && fast.next != null){low = low.next;fast = fast.next.next;if(fast == low){ListNode third = head;while (third != low){third = third.next;low = low.next;}return low;}}return null;}

3. 删除排序链表中的重复元素

OJ:删除排序链表中的重复元素

给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。

示例 1:

输入:head = [1,1,2] 输出:[1,2]

示例 2:

输入:head = [1,1,2,3,3] 输出:[1,2,3]

解题思路

  • 思路1

由于给定的链表是排好序的,因此重复的元素在链表中出现的位置是连续的,因此我们只需要对链表进行一次遍历,就可以删除重复的元素。当cur与cur.next的元素相等时,删除cur.next。下面给出了两种实现方法。

 

public ListNode deleteDuplicates(ListNode head) {      if(head == null || head.next == null){return head;}
//        至少有两个节点
//        头节点val在范围之外if (head == null) {return head;}ListNode cur = head;while (cur.next != null) {if (cur.val == cur.next.val) {cur.next = cur.next.next;} else {cur = cur.next;}}return head;}
public ListNode deleteDuplicates(ListNode head) {if(head ==null ||head.next == null){return null;}head = deleteDuplicates(head.next);return head.val == head.next.val ? head.next : head;}

4. 删除排序链表中的重复元素 II

OJ:删除排序链表中的重复元素 II

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。

示例 1:

输入:head = [1,2,3,3,4,4,5]

输出:[1,2,5]

示例 2:

输入:head = [1,1,1,2,3]

输出:[2,3]

解题思路

    public ListNode deleteDuplicates(ListNode head) {// 1.base caseif (head == null || head.next == null) {return head;}ListNode dummyHead = new ListNode(-101);dummyHead.next = head;ListNode prev = dummyHead;ListNode cur = prev.next;while (cur != null) {ListNode sec = cur.next;if (sec == null) {break;}if (cur.val != sec.val) {prev = prev.next;}else {// 此时cur和sec相等while (sec != null && cur.val == sec.val) {sec = sec.next;}// 此时sec一定走到第一个和cur不相等的结点// prev .. sec全都是待删除的结点prev.next = sec;}cur = sec;}return dummyHead.next;}
 //递归法// 传入一个以head为头节点的链表,就能删除其中所有的重复元素,重复元素一个都不保留public ListNode deleteDuplicates(ListNode head) {// 1.base caseif(head == null || head.next == null) {return head;}if(head.val != head.next.val) {head.next = deleteDuplicates(head.next);return head;}else {// 头节点就是重复的节点,先处理完头节点的情况ListNode newHead = head.next;while(newHead != null && newHead.val == head.val) {newHead = newHead.next;}// 此时newHead一定不是待删除的结点,最终整个传入函数,返回更新后的值即可return deleteDuplicates(newHead);}}

5. 移除链表元素

OJ:移除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

示例 1:

输入:head = [1,2,6,3,4,5,6], val = 6

输出:[1,2,3,4,5]

示例 2:

输入:head = [], val = 1

输出:[]

示例 3:

输入:head = [7,7,7,7], val = 7

输出:[]

解题思路

(1)先判断头节点元素是否与val相等,相等删除头节点(head = head.next)

(2)判断后面的节点元素是否与val相等,相等删除(prev.next = prev.next.next;);不相等往下继续遍历。直至到链表尾部。

    public ListNode removeElements(ListNode head, int val) {while (head != null && head.val == val) {head = head.next;}// 有头节点的链表解法ListNode dummyHead = new ListNode();//与原链表建立联系dummyHead.next = head;ListNode prev = dummyHead;while(prev.next != null){if(prev.next.val == val){prev.next = prev.next.next;}else{prev = prev.next;}}return dummyHead.next;}
public ListNode removeElements(ListNode head, int vals) {if(head == null){return null;}head.next = removeElements(head.next,vals);return head.val == vals ? head.next :head;}

6. 链表的中间结点

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

如果有两个中间结点,则返回第二个中间结点。

示例 1:

输入:head = [1,2,3,4,5]

输出:[3,4,5]

解释:链表只有一个中间结点,值为 3 。

示例 2:

输入:head = [1,2,3,4,5,6]

输出:[4,5,6]

解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。

解题思路

  • 思路1

快慢指针,慢指针走一步,快指针走两步,当快指针走到链表最后一个或走到空时,慢指针走到中间节点。

public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode low = head;while (fast!= null && fast.next != null){low = low.next;fast = fast.next.next;}return low;}
  • 思路2

先求出链表长度,再除以2,就是中间节点的位置了,从链表头遍历到该位置再返回。

    public ListNode middleNode(ListNode head) {int length = 0;ListNode node = head;while(node != null){length++;node = node.next;}length = length / 2;node = head;for(int i =0;i<length;i++){node = node.next;}return node;}

相关文章:

【leetcode】链表(2)

目录 1. 环形链表 解题思路 2. 环形链表 II 解题思路 3. 删除排序链表中的重复元素 解题思路 4. 删除排序链表中的重复元素 II 解题思路 5. 移除链表元素 解题思路 6. 链表的中间结点 解题思路 1. 环形链表 OJ&#xff1a;环形链表 给你一个链表的头节点 head &am…...

使用Vue+vue-router+路由守卫实现路由鉴权功能实战

目录 一、本节介绍和上节回顾 1. 上节介绍 2. Vue SpringBoot前后端分离项目实战的目录 3. 本小节介绍 二、Vue-router改造以及路由鉴权 1. 路由数据的拆分 2. 路由守卫 三、404错误页的实现 1. 创建全局css样式 2. 全局样式引入 3. 404页面的开发 4. el-button的…...

多线程(三):Thread 类的基本属性

上一个篇章浅浅了解了一下 线程的概念&#xff0c;进程与线程的区别&#xff0c;如何实现多线程编程。 而且上一章提到一个重要的面试点&#xff1a; start 方法和 run 方法的区别。 start 方法是从系统那里创建一个新的线程&#xff0c;这个线程会自动调用内部的run 方法&…...

蓝桥杯嵌入式第六课--串口收发

前言串口作为一个考试中考察频率较高的考点&#xff0c;其套路比较固定&#xff0c;因此值得我们仔细把握。本节课主要着眼于快速配置实现 串口收发与串口的中断。CubeMX配置选择串口2配置异步收发模式基本参数设置&#xff08;波特率、校验位等等&#xff09;开启串口收发中断…...

蓝桥杯冲刺 - Lastweek - 你离省一仅剩一步之遥!!!(掌握【DP】冲刺国赛)

文章目录&#x1f4ac;前言&#x1f3af;week3&#x1f332;day10-1背包完全背包多重背包多重背包 II分组背包&#x1f332;day2数字三角形 - 线性DP1015. 摘花生 - 数字三角形&#x1f332;day3最长上升子序列 - 线性DP1017. 怪盗基德的滑翔翼 - LIS1014.登山 - LIS最长公共子…...

C++ map与set的学习

1. 关联式容器在初阶阶段&#xff0c;我们已经接触过STL中的部分容器&#xff0c;比如&#xff1a;vector、list、deque、forward_list(C11)等&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是元素本身。关联式容器也…...

【C语言初阶】函数

文章目录&#x1f490;专栏导读&#x1f490;文章导读&#x1f337;函数是什么&#xff1f;&#x1f337;函数的分类&#x1f33a;库函数&#x1f33a;自定义函数&#x1f337;函数的参数&#x1f337;函数的调用&#x1f337;函数的嵌套调用和链式访问&#x1f33a;嵌套调用&a…...

CentOS 7安装redis6.2.6(包括服务开机自启和开放端口)

CentOS 7安装redis6.2.61. 官网下载redis文件2. 校验安装依赖2.1 安装系统默认版本gcc2.2 升级gcc版本3. 解压编译安装4. 修改配置redis.conf4.2 设置密码4.3 绑定ip&#xff08;可选&#xff09;5. 启动redis服务并测试5.2 测试安装是否成功5.3 redis开机自启配置6.开放防火墙…...

基于注解的自动装配~

Autowired&#xff1a;实现自动装配功能的注解 Autowired注解能够标识的位置&#xff1a; 标识在成员变量上&#xff0c;此时不需要设置成员变量的set方法标识在成员变量对应的set方法上标识在为当前成员变量赋值的有参构造上使用注解进行自动装配&#xff0c;只要在其成员变量…...

【深度学习】【分布式训练】Collective通信操作及Pytorch示例

相关博客 【深度学习】【分布式训练】Collective通信操作及Pytorch示例 【自然语言处理】【大模型】大语言模型BLOOM推理工具测试 【自然语言处理】【大模型】GLM-130B&#xff1a;一个开源双语预训练语言模型 【自然语言处理】【大模型】用于大型Transformer的8-bit矩阵乘法介…...

Spring常用注解说明

目录 1.常用注解 2.特别说明 3.xml及注解方式 1.常用注解 (1) SpringBootApplication (2) ControllerRestControllerRequestMappingRequestParamPathVariableGetMappingPostMappingPutMappingDeleteMappingResponseBodyRequestBodyCrossOrigin (3) ConfigurationBeanServ…...

13-C++面向对象(纯虚函数(抽象类)、多继承、多继承-虚函数、菱形继承、虚继承、静态成员)

虚析构函数 存在父类指针指向子类对象的情况&#xff0c;应该将析构函数声明为虚函数&#xff08;虚析构函数&#xff09; 纯虚函数 纯虚函数&#xff1a;没有函数体且初始化为0的虚函数&#xff0c;用来定义接口规范 抽象类&#xff1a; 含有纯虚函数的类&#xff0c;不可以实…...

Android DataBinding 自定义View实现数据双向绑定

看不懂的可以先看看单向数据绑定&#xff1a;Android DataBinding数据变化时自动更新界面_皮皮高的博客-CSDN博客 然后再确定已经启动了dataBinding的情况下&#xff0c;按下面的顺序来&#xff1a; 首先创建一个自定义View&#xff1a; import android.content.Context imp…...

网络安全中的渗透测试主要那几个方面

渗透测试中主要有软件测试和渗透测试。 1、测试对象不同 软件测试&#xff1a;主要测试的是程序、数据、文档。 渗透测试&#xff1a;对象主要为网络设备、主机操作系统、数据库系统和应用系统。 2、测试内容不同 软件测试&#xff1a;主要工作内容是验证和确认&#xff0c;发…...

Cursor:GPT-4 驱动的强大代码编辑器

Cursor &#xff08;https://www.cursor.so/&#xff09;是 GPT-4 驱动的一款强大代码编辑器&#xff0c;可以辅助程序员进行日常的编码。下面通过一个实际的例子来展示 Cursor 如何帮助你编程。这个例子做的事情是网页抓取。抓取的目标是百度首页上的百度热搜&#xff0c;如下…...

C/C++中for语句循环用法及练习

目录 语法 下面是 for 循环的控制流&#xff1a; 实例 基于范围的for循环(C11) 随堂笔记&#xff01; C语言训练-计算1~N之间所有奇数之和 题目描述 输入格式 输出格式 样例输入 样例输出 环形方阵 干货直达 for 循环允许您编写一个执行特定次数的循环的重复控制结构。…...

AnimatorOverrideController说明

unity-AnimatorOverrideControllerhttps://docs.unity.cn/cn/current/ScriptReference/AnimatorOverrideController.html 用于控制动画器重写控制器的接口。 动画器重写控制器的用途是重写某个控制器的动画剪辑&#xff0c;从而为给定化身定制动画。 在运行时基于相同的 Anim…...

1.4、第三阶段 MySQL数据库

root数据库技术 一、数据库理论 1 什么是数据库技术 数据库技术主要研究如何组织、存储数据&#xff0c;并如何高效地提取和处理数据。 2 什么是SQL SQL&#xff08;Structured Query Language&#xff09;结构化查询语言 SQL是操作数据库的命令集&#xff0c;也是功能齐全的…...

LeetCode:202. 快乐数

&#x1f34e;道阻且长&#xff0c;行则将至。&#x1f353; &#x1f33b;算法&#xff0c;不如说它是一种思考方式&#x1f340;算法专栏&#xff1a; &#x1f449;&#x1f3fb;123 一、&#x1f331;202. 快乐数 题目描述&#xff1a;编写一个算法来判断一个数 n 是不是快…...

Android 14 新功能之 HighLights:快速实现文本高亮~

日常开发中可能会遇到给 TextView 的全部或部分文本增加高亮效果的需求&#xff0c;以前可能是通过 Spannable 或者 Html 标签实现。 升级 Android 14 后就不用这么迂回了&#xff0c;因其首次引入直接设置高亮的 API&#xff1a;HighLights。需要留意的是 HighLights API 和 …...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...