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

Leetcode42-环形链表

题目

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

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

不允许修改 链表。

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

代码

static public ListNode hasCycle_StartNode(ListNode head) {ListNode slow = head, fast = head; // 将 fast 的起始位置设置为 headwhile (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 此时slow和fast在环的中相遇,但是相遇的点不一定是环的入口点,因为进入指针环的时机是不一样的ListNode cycle = head;// 重置一个新节点,走a的距离,就可以和slow后续的移动汇合,且一定是环开始的节点while (cycle != slow) {cycle = cycle.next;slow = slow.next;}return cycle;}}return null;
}

总结

a:从链表头到环的起始节点的距离。
b:从环的起始节点到快慢指针相遇点的距离。
c:环的长度。

慢指针 slow 从头节点开始,走了 a + b 的距离到达相遇点。
快指针 fast 从头节点开始,走了 a + b + n*c 的距离(其中 n 是快指针在环内绕的圈数)。
当快慢指针相遇时,有以下关系:

  • slow 走的距离:a + b
  • fast 走的距离:a + b + n*c

由于快指针的速度是慢指针的两倍,得出: 2(a + b) = a + b + nc => a + b = nc
这表明慢指针走的距离a+b是环长度的整数倍

http://www.lryc.cn/news/505417.html

相关文章:

  • C语言进阶(2) ---- 指针的进阶
  • 使用Python筛选图片
  • GESP CCF python五级编程等级考试认证真题 2024年12月
  • URL的概念与格式
  • 【Elasticsearch】高亮搜索:从原理到Web呈现
  • samout llm解码 幻觉更低更稳定
  • 单片机:实现多任务处理(附带源码)
  • 负载均衡oj项目:介绍
  • 剑指Offer 03比特位计数
  • 多音轨视频使用FFmpeg删除不要音轨方法
  • elasticsearch 使用enrich processor填充数据
  • VMProtect:软件保护与安全的全面解决方案
  • Web 毕设篇-适合小白、初级入门练手的 Spring Boot Web 毕业设计项目:教室信息管理系统(前后端源码 + 数据库 sql 脚本)
  • 第十二篇:linux下socket本地套接字通讯
  • Spring Boot 2.1.7 数据源自动加载过程详解
  • 【Vue.js 3.0】provide 、inject 函数详解
  • JVM(Java虚拟机)的虚拟机栈
  • Elasticsearch02-安装7.x
  • iPhone恢复技巧:如何从 iPhone 恢复丢失的照片
  • vba批量化调整word的图和图表标题
  • 【Flutter_Web】Flutter编译Web第二篇(webview篇):flutter_inappwebview如何改造方法,变成web之后数据如何交互
  • 【C语言的奥秘11】指针知识点总结(续)
  • excel 列名是数据表 的字段名 ,单元格的值 是数据表对应字段的值,生成sql插入语句
  • AI Agent与MEME:技术与文化融合驱动Web3创新
  • IO的入门
  • 构建一个rust生产应用读书笔记四(实战1)
  • SpringCloudAlibaba | Sentinel从基础到进阶
  • 算法刷题Day18: BM41 输出二叉树的右视图
  • 【信息系统项目管理师-论文真题】2015下半年论文详解(包括解题思路和写作要点)
  • Windows如何安装go环境,离线安装beego