描述
給定一個(gè)鏈表，判斷它是否有環(huán)摊沉。
樣例
給出 -21->10->4->5, tail connects to node index 1狐史，返回 true
挑戰(zhàn)
不要使用額外的空間
思路
- 使用O(n)的額外空間時(shí)，在遍歷整個(gè)鏈表的過(guò)程中用一個(gè)hash表存儲(chǔ)當(dāng)前結(jié)點(diǎn)的引用，如果hash表中已經(jīng)存在當(dāng)前結(jié)點(diǎn)的引用return false骏全，否則加入hash表苍柏，如果遍歷完整個(gè)鏈表仍舊沒(méi)發(fā)現(xiàn)重復(fù)值證明鏈表沒(méi)環(huán)
- 定義兩個(gè)指針，一個(gè)快一個(gè)慢姜贡，設(shè)定快的跑兩步试吁，慢的跑一步，如果有環(huán)則它們一定會(huì)相遇
兩種思路時(shí)間復(fù)雜度都是O(n)
變形題目
題目有一種變體楼咳，就是判斷兩個(gè)鏈表有沒(méi)有交集熄捍，將第一個(gè)鏈表的末指針和第二個(gè)鏈表的頭指針連接到一起，若有交集則一定存在環(huán)
代碼
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
- 哈希表法
public class Solution {
/*
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
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;
}
}
- 快慢指針
public class Solution {
/*
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
// 注意要讓跑的快的在前面母怜，不然沒(méi)跑完一圈就追上了
ListNode slow = head;
// 如果 fast 也賦值為 head 則在第一個(gè)結(jié)點(diǎn)就會(huì)跳出 while 循環(huán)
ListNode fast = head.next;
while (slow != fast) {
// 在沒(méi)追上慢指針的情況下余耽，遍歷完了整個(gè)鏈表，證明沒(méi)有環(huán)
if (fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
// slow == fast時(shí)證明有環(huán)
return true;
}
}
