給定一個鏈表，判斷鏈表中是否有環(huán)。
為了表示給定鏈表中的環(huán)嘹锁，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1阀湿，則在該鏈表中沒有環(huán)赶熟。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點陷嘴。
解法1：快慢指針映砖，
/**
* 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) {
if(head == null || head.next == null)
return false;
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast){
if(fast == null || fast.next == null ){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
思路
我們可以通過檢查一個結(jié)點此前是否被訪問過來判斷鏈表是否為環(huán)形鏈表。常用的方法是使用哈希表灾挨。
算法
我們遍歷所有結(jié)點并在哈希表中存儲每個結(jié)點的引用（或內(nèi)存地址）邑退。如果當前結(jié)點為空結(jié)點 null（即已檢測到鏈表尾部的下一個結(jié)點），那么我們已經(jīng)遍歷完整個鏈表劳澄，并且該鏈表不是環(huán)形鏈表地技。如果當前結(jié)點的引用已經(jīng)存在于哈希表中，那么返回 true（即該鏈表為環(huán)形鏈表）秒拔。
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
復雜度分析
時間復雜度：O(n)莫矗，對于含有 n 個元素的鏈表，我們訪問每個元素最多一次砂缩。添加一個結(jié)點到哈希表中只需要花費 O(1) 的時間作谚。
空間復雜度：O(n)，空間取決于添加到哈希表中的元素數(shù)目庵芭，最多可以添加 n 個元素妹懒。
