141. 環(huán)形鏈表 - 力扣（LeetCode）
142. 環(huán)形鏈表 II - 力扣（LeetCode）
題解：
快慢指針題
從head開始，一個快指針，一次前進兩步，一個慢指針，一次走一步
如果沒有環(huán)，則快指針首先到達鏈表尾部，
如果有環(huán)，快慢指針肯定能相遇即fast=slow
141代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-762997.html
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(slow && fast && fast->next)//這里的slow可以不用判斷
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast) return true;
}
return false;
}
};對于142需要環(huán)的起點，需要找出其中規(guī)律，動手畫一下，當slow與fast相等的時候，假設slow從head開始走了k步，那么此時fast走了2k步，fast多走的k步是鏈表環(huán)的大小，假設相遇時，環(huán)起點與相遇點的距離為n,則head距離環(huán)啟動的距離為k-n,slow繼續(xù)往前走，距離環(huán)起點的距離也為k-n,所以此時任意一個指針從head開始，每次前進一步，剛好在環(huán)起點與slow相遇。代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-762997.html
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == nullptr) return head;
ListNode* slow = head;
ListNode* fast = head;
while(fast != nullptr && slow != nullptr)
{
slow = slow->next;
fast = fast->next;
if(fast != nullptr)
fast = fast->next;
if(fast == slow)
break;
}
if(fast == nullptr) return nullptr;
fast = head;
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
};到了這里，關于LeetCode[141] [142] 環(huán)形鏈表I II的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
