環形鏈表 | 和 || 題型相似且 || 是 | 的升級版，故放一起，
1.題 | 如下：
2.題目分析：
回傳的是一個布爾型的結果，如果有環回傳true，無環回傳false，
3.源代碼：
bool hasCycle(struct ListNode *head) {
if(head==NULL)
return false;
struct ListNode *solw=head;
struct ListNode *fast=head;
while(fast && fast->next){
solw=solw->next;
fast=fast->next->next;//使快指標比慢指標快二步
if(solw==fast){
return true;//快慢指標相遇即有環
}
}
return false;//無環
}
1.題 || 如下：
2.題目分析：
3.源代碼：
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow=head;
struct ListNode* fast=head;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
break;//判斷有環
}
if(fast==NULL||fast->next==NULL){
return NULL;//無環情況
}
else{
struct ListNode* meet=slow;
while(1){//由題目分析推斷關系得如下且用while（1）死回圈
if(meet==head)
break;//一定是先判斷保證情況二也可以考慮到
head=head->next;
meet=meet->next;
}
return meet;
}
return 0;
}
4.總結：
1.解決類似問題以及鏈表中的問題可以多考慮用快慢指標解決，
2. 解決的第二題為什么快指標要比慢指標快二倍不可以是別的：
如果是三步：X X-2 X-4 X-6…如果X是奇數快慢指標就會錯過不會像兩步一樣每走一步之間的距離每縮小一步，類推別的也就不可以，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/241360.html
標籤：其他