題目描述
給定一個(gè)鏈表埋泵，判斷鏈表中是否有環(huán)。
為了表示給定鏈表中的環(huán)罪治，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）丽声。 如果 pos 是 -1，則在該鏈表中沒有環(huán)觉义。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)雁社，其尾部連接到第二個(gè)節(jié)點(diǎn)。
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個(gè)環(huán)晒骇，其尾部連接到第一個(gè)節(jié)點(diǎn)霉撵。
題目解析
方法一：哈希表
解題思路
首先可以想到的方法就是遍歷鏈表并將遍歷的鏈表Node節(jié)點(diǎn)存入哈希表中，通過哈希表是判斷Node是否已經(jīng)存在洪囤，若已經(jīng)存在則說明鏈表存在環(huán)喊巍，否則無環(huán)。
代碼示例
Java：
/*
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode curr = head;
while (curr != null) {
if (visited.contains(curr)) {
return true;
}
visited.add(curr);
curr = curr.next;
}
return false;
}
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)箍鼓，通過額外空間存儲(chǔ)遍歷節(jié)點(diǎn)
方法二：雙指針
解題思路
假設(shè)鏈表存在環(huán)崭参，若兩個(gè)遍歷速率不一樣的指針同時(shí)遍歷整個(gè)鏈表，這兩個(gè)指針最終會(huì)相遇款咖。所以我們可以采用 快慢指針 的方式將空間復(fù)雜度優(yōu)化到O(1)何暮。慢指針slow每次遍歷一個(gè)節(jié)點(diǎn)，快指針fast每次遍歷兩個(gè)節(jié)點(diǎn)铐殃，直到指針走到鏈表末尾或者兩個(gè)指針相遇海洼。
代碼示例
Java：
/*
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)
