1.題目

給你一個鏈表的頭節點 head ，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數進行傳遞?。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環?，則返回 true 。 否則，返回 false 。

2.示例

示例 1：

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

?示例?2：

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

?示例 3：

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

提示：鏈表中的結構體

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/

3.思路

快慢指針：

像這種循環題目或者是追逐的題目就可以使用快慢指針算法，由于是循環的，那么除非快指針先找到null的情況下，快慢指針必定相遇，并且兩者的相遇也就意味著鏈表的循環，因為一般情況下快指針是走的快的，慢指針走的慢，而兩者速度明顯不同的情況下卻相遇了，那就說明鏈表是循環的

哈希集合：

由于循環最后就是查看是否有重合后的地址，那么只需要在往下遍歷的時候將鏈表節點地址保存起來，在下一次遍歷的時候如果下一個節點地址已經存在與哈希表中時候，那么也就意味著鏈表是循環的

4.代碼

LeetCode代碼

快慢指針：

public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false; // 鏈表為空或只有一個節點，必然無環}ListNode slowIndex = head;ListNode fastIndex = head;while (fastIndex != null && fastIndex.next != null) {slowIndex = slowIndex.next; // 慢指針每次移動一個節點fastIndex = fastIndex.next.next; // 快指針每次移動兩個節點if (slowIndex == fastIndex) {return true; // 快慢指針相遇，存在環}}return false; // 快指針到達鏈表尾部，無環}
}

?時間復雜度O(n)，空間復雜度O(1)

?哈希集合：

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

?時間復雜度O(n)，空間復雜度O(n)?

---

會了？試試挑戰下一題！?（＾?＾●）ﾉｼ （●′?｀）?

LeetCode150道面試經典題-- 合并兩個有序鏈表(簡單)_Alphamilk的博客-CSDN博客