給定一個(gè)鏈表衣迷，判斷鏈表中是否有環(huán)畏鼓。
進(jìn)階：
你能否不使用額外空間解決此題？
解法1：
思路： 比較六的思路壶谒，我用兩指針fast和low云矫，從頭開始，一個(gè)走兩步汗菜，一個(gè)走一步让禀。
如果有環(huán)，就一定有追上的時(shí)候陨界。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode* head) {
if(head == NULL||head->next == NULL){
return false;
}
struct ListNode* fast=head->next;
struct ListNode* low=head;
while(fast!=NULL){
if(fast==low){
return true;
}else{
fast=fast->next;
if(fast==NULL){
return false;
}else{
fast=fast->next;
low=low->next;
}
}
}
return false;
}
解法2：
思路： leetcode給出的解法：我們遍歷所有結(jié)點(diǎn)并在哈希表中存儲(chǔ)每個(gè)結(jié)點(diǎn)的引用（或內(nèi)存地址）巡揍。如果當(dāng)前結(jié)點(diǎn)為空結(jié)點(diǎn) null（即已檢測到鏈表尾部的下一個(gè)結(jié)點(diǎn)），那么我們已經(jīng)遍歷完整個(gè)鏈表菌瘪，并且該鏈表不是環(huán)形鏈表腮敌。如果當(dāng)前結(jié)點(diǎn)的引用已經(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;
}
