leetcode--环形链表.找到入环节点(java)

news/2024/10/31 5:33:32/

环形链表II

  • 环形链表.找到入环节点
  • 题目描述
  • 解题思路

环形链表.找到入环节点

LeetCode 142:环形链表II 可以在这里测试

题目描述

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

示例1:
在这里插入图片描述

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

示例2:
在这里插入图片描述

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

示例3:
在这里插入图片描述

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

解题思路

这里用到一个小技巧,快慢指针法:
1.环形链表没有尾结点,会在环里循环,因此,如果能走到null ,就表示无环,
2.有环时,使用快慢指针法,快指针一次走两步,慢指针一次走一步,一定会在环内相遇,
3.相遇后,快指针回到头节点,然后改成每次走一步,慢指针还是走一步。然后就会在入环节点相遇。
4.上面的结论,自己可以试着证明下。

代码如下:

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {//环形链表 没有null 节点,如果走到null 说明无环,if(head == null || head.next == null || head.next.next == null){return null;}//快的先走两步,慢的走一步ListNode fast = head.next.next;ListNode slow = head.next;//先让快慢指针相遇while(fast != slow){//遇到null 说明无环if(fast.next == null || fast.next.next == null){return null;}fast = fast.next.next;slow = slow.next;}//快指针回到头节点,开始一次走一步,就会在入环节点相遇fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return slow;}
}

创作不易,一键三连


http://www.ppmy.cn/news/88886.html

相关文章

十八、map和set

文章目录 一、关联式容器(一)序列式容器:(二)关联式容器: 二、树形结构与哈希结构(一)树型结构(二)哈希结构 三、键值对四、set五、multiset六、map&#xff…

11省政企单位密集调研实在智能数字员工

当前,数字中国建设迎来前所未有的发展机遇。五月,“数字中国”建设持续如火如荼,实在智能又迎来了新的“考察团路线”:西部新宁甘云中轴线晋豫鄂湘东部鲁苏闽,来自11省,20余个“数字化改革政企考察团”&…

2023年湖北助理工程师个人申报怎么申请?

这是许多出入职场的人,比较关心的话题,想要申请一个助理工程师怎么办呢?助理职称好不好办?助理工程师职称个人怎么申请呢?助理工程师申需要什么材料呢?助理工程师申报有什么流程呢?甘建二现在教…

代码随想录算法训练营第52天 |300、674、718

300. 最长递增子序列 题目描述 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2…

第三方实验室云LIS系统

本套云LIS系统基于B/S架构的实验室管理系统,整个系统的运行基于WEB层面,只需要在对应的工作台安装一个浏览器软件有外网即可访问。SaaS服务,无需部署,开通账号接口快速入门使用,集齐前处理、检验、报告、质控、统计分析…

【Go语言从入门到实战】面向对象编程篇

面向对象编程 Go语言的面向对象编程和其他语言有非常大的差别。 Go 是一种面向对象的语言吗? 是和不是。虽然 Go 有类型和方法,并允许面向对象的编程风格,但没有类型层次结构(继承)。Go 中的“接口”概念提供了一种不…

互联网医院系统的优势与挑战:现状调研分析

随着互联网技术的不断发展和普及,互联网医院系统也逐渐走进人们的视野。这种以互联网技术为支撑的医疗服务模式,可以为患者提供更加便捷、快速和高效的医疗服务,同时也可以缓解医院资源短缺的问题。 一、互联网医院系统的优势 方便快捷 互联…

linuxOPS基础_linux安装配置

Linux系统下载 Linux系统版本选择:CentOS7.6 x64,【镜像一般都是CentOS*.iso文件】 问题:为什么不选择最新版的8 版本? 7.x 目前依然是主流 7.x 的各种系统操作模式是基础 官网:https://www.centos.org/ ,…