LeetCode[141] [142] 环形链表I II-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode[141] [142] 环形链表I II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

141. 环形链表 - 力扣（LeetCode）

142. 环形链表 II - 力扣（LeetCode）

题解：

快慢指针题

从head开始，一个快指针，一次前进两步，一个慢指针，一次走一步

如果没有环，则快指针首先到达链表尾部，

如果有环，快慢指针肯定能相遇即fast=slow

141代码：

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需要环的起点，需要找出其中规律，动手画一下，当slow与fast相等的时候，假设slow从head开始走了k步，那么此时fast走了2k步，fast多走的k步是链表环的大小，假设相遇时，环起点与相遇点的距离为n,则head距离环启动的距离为k-n,slow继续往前走，距离环起点的距离也为k-n,所以此时任意一个指针从head开始，每次前进一步，刚好在环起点与slow相遇。代码如下：文章来源地址https://www.toymoban.com/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] 环形链表I II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！