hot100---环形链表

141. 环形链表 - 力扣LeetCode给你一个链表的头节点head判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。注意pos不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环则返回true。 否则返回false。1. 方法一思路用HashSet充当“便利贴集合”。遍历链表每到一个节点就试图把它放进HashSet贴上便利贴。如果放进去时发现它已经存在了已经被贴上便利贴了说明链表有环。如果顺利走到了null说明链表没有环。代码/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val x; * next null; * } * } */ /** * 使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点如果该节点已经存在于哈希表中则说明该链表是环形链表否则就将该节点加入哈希表中。重复这一过程直到我们遍历完整个链表即可。 */ public class Solution { public boolean hasCycle(ListNode head) { // 1. 创建一个哈希集合用来存储“已经访问过”的节点 SetListNode seen new HashSet(); // 2. 遍历链表 while (head ! null) { // 3. 尝试把当前节点加入集合 // add() 方法会返回 boolean // - 如果集合中还没有这个节点添加成功返回 true // - 如果集合中已经有了这个节点添加失败返回 false if (!seen.add(head)) { // !true false不加!false true进入 if return true; // 节点重复出现 → 有环 } // 4. 移动到下一个节点 head head.next; } // 5. 走到链表末尾 (null) 都没发现重复节点 → 无环 return false; } }细节补充①SetListNode seen new HashSet();Set一个不包含重复元素的集合。HashSetSet最常用的实现底层是哈希表增删查平均都是 O(1)。这里存的不是节点的值而是节点对象的引用地址。HashSet比较对象时用的是equals和hashCode默认比较内存地址所以能精确识别出同一个节点。所以即使两个不同节点的值相同也会被当成不同的节点这正是我们需要的——我们要判断的是同一个节点被多次访问。②if (!seen.add(head))add方法如果集合中还没有这个元素就把它加进去并返回true如果已经有了就什么都不做并返回false。所以!seen.add(head)的意思是如果没有添加成功即已经存在就执行return true代表发现了环。复杂度时间复杂度O(n)每个节点最多访问一次有环时重复的那个节点被访问第二次时就会退出。空间复杂度O(n)最坏情况下需要存储所有节点的引用。2. 方法二思路龟兔赛跑slow乌龟一次走1步。fast兔子一次走2步。如果链表是直的无环兔子会先跑到终点null比赛结束。如果链表中有圆圈有环兔子会在圈里不断跑而且因为兔子的速度是乌龟的两倍兔子一定会从后面追上乌龟两者在圈内某个点相遇。代码public class Solution { public boolean hasCycle(ListNode head) { ListNode slow head, fast head; // 乌龟和兔子同时从起点出发 while (fast ! null fast.next ! null) { // 兔子能跑就继续 fast fast.next.next; // 兔子走两步 slow slow.next; // 乌龟走一步 if (fast slow) { // 兔子追上乌龟 → 有环 return true; } } return false; // 兔子跑到终点null→ 无环 } }细节补充while (fast ! null fast.next ! null)fast ! null防止兔子自己踩空当前节点不能是null。fast.next ! null防止兔子走第二步时踩空要取fast.next.next必须保证fast.next存在。如果链表无环兔子最先触碰到null循环就结束了。fast fast.next.next;兔子走两步因为前面已经保证了fast和fast.next非空所以这一步安全。if (fast slow) return true;比较的是两个引用是否指向同一个节点对象。如果相遇说明兔子在环内追上了乌龟。复杂度时间复杂度O(n)无环时兔子跑完全程有环时乌龟最多走一圈兔子最多走两圈。总体上每个节点被访问常数次。空间复杂度O(1)只用了两个额外指针没有占用额外内存。3. 相关知识补充Set接口和HashSet类Set不包含重复元素允许最多一个null。HashSet基于哈希表add、contains、remove都是 O(1)。add方法的返回值boolean add(E e)如果集合尚未包含e添加并返回true如果已包含返回false。对象的相等性默认情况下HashSet使用hashCode()和equals()来判断两个对象是否相同。ListNode没有重写这两个方法因此比较的是内存地址正好是我们需要的“是不是同一个节点”。