立志用最少的代碼做最高效的表達

---

給定一個鏈表，判斷鏈表中是否有環。
如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。
如果鏈表中存在環，則返回 true 。 否則，返回 false 。

示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環。

提示：
鏈表中節點的數目范圍是 [0, 104]
-105 <= Node.val <= 105
pos 為 -1 或者鏈表中的一個 有效索引 。

---

解法一：hash表

使用hashset判重。 最初使用value判重，若value重復則判定節點重復，提交后出錯。

仔細審題后發現，節點的值是有可能相同的。

因此改變思路，用容器存儲節點本身。

這樣判定節點是否相等就變成了判斷地址是否相等，若地址相等，則一定出現了環。

優化：將HashMap修改為HashSet，時間上可以更快一些。

時間復雜度：O(n)
空間復雜度：O(n)

public class Solution {public boolean hasCycle(ListNode head) {Set<ListNode> set = new HashSet<>();while(head != null) {if(set.contains(head)) return true;set.add(head);head=head.next;}return false;} }

---

解法二：快慢指針法

定義兩個指針fast和slow，fast每次走兩步，slow每次走一步，若fast追上了slow，則代表存在環。若fast == null，則代表無環。

注意：一定注意程序的健壯性，即指針不能指向null。

時間復雜度：O(n)
空間復雜度：O(1)

public class Solution {public boolean hasCycle(ListNode head) {if(head == null) return false;ListNode fast = head, slow = head;while(slow != null && slow.next != null && slow.next.next != null) { // 魯棒性slow = slow.next.next;fast = fast.next;if(slow == fast) return true;}return false;} }

---

木秀于林，風必摧之；堆出于岸，流必湍之；行高于人，眾必非之。

總結

以上是生活随笔為你收集整理的【双100%解法】LeetCode 141 【剑指Offer 23】链表中环的入口节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。