[链表专题]力扣141, 142

1. 力扣141 : 环形链表

题 : 

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

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

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

示例 1:

03200a8deef086fed38c83518d504ffe.png

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

1030fe4a5f06ecbc6fbeb811df4aa81e.png

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

50866d36074ce3fcc11a3fe0da496954.png

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

提示:

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

进阶:你能用 O(1)(即,常量)内存解决此问题吗?

思路 : 如果是空链表,直接返回false.如果是环形链表,那么p以及p.next一定不为null.p的移动速度比q快.所以p一定会追赶上q(p==q).所以此时返回true.否则返回flase.

解 : 

public class Solution {public boolean hasCycle(ListNode head) {if (head == null) {return false;}ListNode p = head;ListNode q = head;while(p != null && p.next != null) {p = p.next.next;q = q.next;if (p == q) {return true;}}return false;}
}

2. 力扣142 : 环形链表2

题 : 

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

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

不允许修改 链表。

示例 1:

bfa82ae81e8b0831323bfdb9f22681a5.png

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

1f891a7b41cc5919c33f6fd909936190.png

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

eb33678530842daa48a4c1c4b42d8976.png

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

进阶:你是否可以使用 O(1) 空间解决此题?

思路 : 

解 : 

public class Solution {public ListNode detectCycle(ListNode head) {ListNode p = head;ListNode q = head;while (p != null && p.next != null) {p = p.next.next;q = q.next;if (p == q) {q = head;while(q != p) {p = p.next;q = q.next;}return p;}}return null;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/328613.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

洛谷P1364 医院设置

P1364 医院设置 题目描述 设有一棵二叉树&#xff0c;如图&#xff1a; 其中&#xff0c;圈中的数字表示结点中居民的人口。圈边上数字表示结点编号&#xff0c;现在要求在某个结点上建立一个医院&#xff0c;使所有居民所走的路程之和为最小&#xff0c;同时约定&#xff0c…

20240511每日运维----聊聊nignx改配置所有的nginx改完unknow

1、改配置所有的nginx改完unknow src/core/nginx.h src/http/ngx_http_header_filter_module.c src/http/ngx_http_special_response.c src/http/v2/ngx_http_v2_filter_module.c 2、make 3、去objs里面把nginx文件替换过去sbin/nginx

从JSON数据到Pandas DataFrame:如何解析出所需字段

目录 一、引言 二、JSON数据的基本结构 三、使用Pandas从JSON数据中读取数据 四、从DataFrame中解析出所需字段 解析对象字段 解析嵌套对象字段 解析数组字段 五、案例与代码示例 六、总结 一、引言 在数据分析和处理的日常工作中&#xff0c;我们经常需要从各种…

Python悬置动刚度模拟及复数绘制

Python悬置动刚度模拟及复数绘制 1、复数绘制极坐标图2、动刚度的计算公式3、悬置动刚度的影响因素4、 AVL Excite 悬置动刚度的模拟 1、复数绘制极坐标图 # _*_ coding:UTF-8 _*_import matplotlib.pyplot as plt import numpy as np# 定义复数数组 complexNums [1.5 1.2j,…

参考文献自检指南

参考文献作为论文的最后组成部分&#xff0c;可能不是加分项&#xff0c;但是做不好的话绝对会被吐槽&#xff0c;而且是个要命的减分项。因此要做好检查&#xff0c;以下是一些可以遵循的规范。&#xff08;如有疏漏&#xff0c;欢迎指出&#xff09; .bib文件 1.字段的选…

战网国际服下载教程 暴雪战网客户端一键下载安装教程分享

战网国际服务平台&#xff0c;又名Battle.net环球版&#xff0c;是暴雪娱乐操作的跨国界游戏交流平台&#xff0c;它消除了地域的隔阂&#xff0c;向全球范围内的游戏爱好者提供服务。与仅服务于特定地区的版本不同&#xff0c;国际版赋予了玩家自由穿梭于暴雪众多标志性游戏的…

解决ubuntu无法上网问题

发现是网络配置成了Manual手动模式&#xff0c;现在都改成自动分配DHCP模式 打开后&#xff0c;尝试上网还是不行&#xff0c;ifconfig查看ip地址还是老地址&#xff0c;怀疑更改没生效&#xff0c;于是重启试试。 重启后&#xff0c;ip地址变了&#xff0c;可以打开网页了 …

python高级爱心代码

python高级爱心代码实现&#xff1a; import turtle import random # 设置画布 screen turtle.Screen() screen.bgcolor("black") # 创建画笔 pen turtle.Turtle() pen.speed(0) pen.color("red") pen.penup() # 移动画笔到起始位置 pen.goto(0, -20…

(实测验证)【移远EC800M-CN 】TCP 透传

引言 本文章使用自研“超小体积TTL转4GGPS集成模块”进行实测验证&#xff1b; 1、配置移远EC800M-CN TCP 透传 串口助手发送&#xff1a; ATQIOPEN1,0,"TCP","36.137.226.30",39755,0,2 //配置服务器地址和端口号&#xff1b; 4G模组返回…

【SpringBoot】SpringBoot整合jasypt进行重要数据加密

&#x1f4dd;个人主页&#xff1a;哈__ 期待您的关注 目录 &#x1f4d5;jasypt简介 &#x1f525;SpringBoot使用jasypt &#x1f4c2;创建我需要的数据库文件 &#x1f4d5;引入依赖 &#x1f513;配置数据库文件&#xff08;先不进行加密&#xff09; &#x1f319;创…

2、快速搭建Vue框架以及项目工程

本篇文章详细讲解在配置完vue2环境后如何快速搭建一个Vue框架和项目工程。&#xff08;以智慧农业云平台为例&#xff09; 2.1 Vue工程创建 2.1.1创建想要存放的Vue文件夹 找到想要存放的文件夹并在目录搜索框中&#xff0c;并用管理员的方式打开。 2.1.2创建Vue工程 2、安装…

【qt】动态属性

这里写目录标题 一.属性1.属性的好处2.添加属性3.使用属性 二.只读属性 一.属性 1.属性的好处 说到属性&#xff08;property&#xff09;&#xff0c;你们会想到什么&#xff1f;我会联想到特点&#xff0c;就是一类对象所特有的&#xff0c;在C中&#xff0c;成员数据就是这…

【Linux 网络】网络基础(二)(应用层协议:HTTP、HTTPS)-- 详解

我们程序员写的一个个解决我们实际问题&#xff0c;满足我们日常需求的网络程序&#xff0c;都是在应用层。 前面写的套接字接口都是传输层经过对 UDP 和 TCP 数据发送能力的包装&#xff0c;以文件的形式呈现给我们&#xff0c;让我们可以进行应用层编程。换而言之&#xff0c…

nginx--FastCGI

CGI 概念 nginx通过与第三方基于协议实现&#xff0c;即通过某种特定协议将客户端请求转发给第三方服务处理&#xff0c;第三方服务器会新建新的进程处理用户的请求&#xff0c;处理完成后返回数据给Nginx并回收进程(下次处理有需要新建)&#xff0c;最后nginx在返回给客户端…

HTTP客户端手动解析响应体数据

服务端 package mainimport ("easyGo/person""encoding/json""net/http" )func main() {http.HandleFunc("/test", func(w http.ResponseWriter, r *http.Request) {p : &person.Person{Name: "jackie",Age: 30,T: pe…

简单记录下:Navicat 导出表结构至 Excel

首先我们需要通过sql语句查询出相关的表结构的结构 SELECT COLUMN_NAME AS 字段名称,COLUMN_TYPE AS 字段类型,IF(IS_NULLABLENO,否,是) AS 是否必填,COLUMN_COMMENT AS 注释FROM INFORMATION_SCHEMA.COLUMNSWHERE table_schema bs-gdsAND table_name sys_menu;查询的结构如下…

JavaScript-基本数据类型和变量

基本数据类型 JavaScript支持数字、字符串和布尔值3种基本数据类型 字符串型 字符串型是JavaScript用来表示文本的数据类型&#xff0c;字符串通常由单引号或双引号括起来&#xff0c;如果字符串存在特殊字符&#xff0c;可以用转义字符代替 数字型 数字型也是JavaScript中的基…

【软考】模拟考卷错题本2024-05-14

1 活动图-计算时间差 审题&#xff0c;第几天~选的3、10是结束了上一次的活动并未开始呢 &#xff01;所以记得按照正常的语序表达哦&#xff01; 2 队列-算长度 代入法&#xff0c;设计一个开始为0&#xff0c;结尾为9 &#xff0c;容量为10即M的队列&#xff1b;带入计算当前…

【class4】建立人工智能系统(1)

【class4】 【回顾class】 上上次的课程里&#xff0c;我们使用csv模块读取了一份CSV文件。 该文件里存储了各电商平台上对某品牌电视机的评价&#xff0c;以及每条评价所对应的正负面性。 我们将读取后的数据存储在了列表data里。 对应的代码&#xff1a; # 导入csv模块 im…

GD32F103RCT6/GD32F303RCT6(9)高级定时器互补PWM波输出实验

本文章基于兆易创新GD32 MCU所提供的2.2.4版本库函数开发 后续项目主要在下面该专栏中发布&#xff1a; 手把手教你嵌入式国产化_不及你的温柔的博客-CSDN博客 感兴趣的点个关注收藏一下吧! 电机驱动开发可以跳转&#xff1a; 手把手教你嵌入式国产化-实战项目-无刷电机驱动&am…