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

环形链表II-leetcode

题目描述

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

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

不允许修改 链表。

示例 1:

img

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

示例 2:

img

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

示例 3:

img

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

提示:

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

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

解法一

思路:

采用哈希表,依次遍历所有的节点,若当前节点在哈希表中出现,那么返回该节点。

/*** 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) {if (head == null || head.next == null) return null;Set<ListNode> set = new HashSet<>();ListNode p=head;while (p!=null) {if(set.contains(p)) return p;set.add(p);p = p.next;}return null;}
}

解法二

思路:

采用快慢指针的方法,当快慢指针相遇的时候,那么现在肯定在环内,此时再设置一个指针,从头指针开始,依次向后移动,同时,slow指针也向后移动。若他们相遇则就是入环点。

证明:

image-20250929190631617

image-20250929190609824

image-20250929190654791

代码:

/*** 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) {ListNode slow = head;ListNode fast = head;ListNode ptr = head;boolean flag = false;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast){flag=true;break;}}if (!flag)return null;while(true){if(ptr == slow)return slow;slow = slow.next;ptr = ptr.next;}}
}
http://www.hskmm.com/?act=detail&tid=21057

相关文章:

  • ubuntu20.04安装nvidia显卡
  • [线段树系列 #6] 标记永久化
  • 9.29
  • c语言switch和if语句
  • Qt(制作一个方便的文本编辑器)
  • Java EE初阶启程记05---线程安全 - 指南
  • DataGridView表格控件使用说明
  • 题解:P7126 [Ynoi2008] rdCcot
  • 个人微信机器人开发api接口
  • MyBatis技术详解:从入门到高效开发 - 详解
  • 解码数据结构队列
  • 解决升级 Windows 11 24H2 后 NAS 共享无法显示的问题
  • 【还未找到原题】宝石(GEM) - Harvey
  • 第八篇
  • C# AStar 算法 - 实际应用
  • nocobase 源码安装
  • 航司网站url后缀参数FECU分析
  • 子网掩码完全指南:从入门到精通
  • 微信群机器人API
  • 9月29号
  • 【CF19E】Fairy - Harvey
  • Python从入门到实战 (14):工具落地:用 PyInstaller 打包 Python 脚本为可执行文件 - 实践
  • Harmony实现流转开发之音乐播放器跨设备流转 - 实践
  • 软件工程中线性回归应用
  • 解决秒杀高并发的一些方案
  • 构建移动网关:Air780EPM用4G为WiFi和LAN设备供网
  • 9.29模拟赛总结
  • 多corner综合
  • 优化 if/else 的四种设计模式
  • Day11-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\oop\demo06