【力扣每日一题】2023.7.30 环形链表2-Toy模板网

这篇具有很好参考价值的文章主要介绍了【力扣每日一题】2023.7.30 环形链表2。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

【力扣每日一题】2023.7.30 环形链表2,力扣每日一题,leetcode,链表,算法,数据结构,c++

示例：

【力扣每日一题】2023.7.30 环形链表2,力扣每日一题,leetcode,链表,算法,数据结构,c++

分析：

这道题属于是那种知道解法就很简单，不知道解法就很难独立想出来的那种，我们只需要稍微记住这类题的固定解法就可以。

所以接下来我先说解法，再解释为什么解法可以解出来。

那么我们都知道使用快慢指针可以找出一个链表是否有环（不知道的去看看我昨天的每日一题题解），我们需要找出这个环的路口，我们在快慢指针相遇的时候就可以判断出链表有环，并且开始寻找。

我们将快指针移动回链表的开头，并且将快指针的速度调整为每次移动一格，然后再让快慢指针再次移动，直到它们相遇，相遇的位置就是环的入口。

这看起来有些不可思议是吗，怎么会这么简单，而且怎么就可以知道它们再次相遇的点就是环入口了，~~小朋友你是否有很多问号？？？~~

那么这涉及到了数学，因此这类题我的建议就是记住对应的模板，不要深究怎么样才可以在下次遇到类似的题目时自己可以从零开始推导出来~~，这不是普通人能干的~~。

首先我们把链表开头到环入口的这段距离称为A，把环入口到快慢指针第一次相遇的地方的这段距离称为B，把快慢指针第一次相遇的地方直走走回环的入口的这段距离称为C，接下来可以开始推导了。

【力扣每日一题】2023.7.30 环形链表2,力扣每日一题,leetcode,链表,算法,数据结构,c++

我们知道，快指针走过的的路程等于A+B+C+B，而慢指针走过的路程等于A+B。

我们又知道，每次快指针移动两格，慢指针移动一格，因此快指针走过的路程是慢指针的两倍。

我们就可以得到这样的式子：

A+B+C+B = 2*（A+B） = A+A+B+B

化简一下就变成了：

C=A

神奇吗同志们，从链表到环入口的距离（A）就等于在快慢指针第一次相遇的地方再次走到环入口，因此我们之前的操作就可以得到解释了，让慢指针接着走，然后让快指针调整速度以后从头开始走，走到它们第二次相遇，那就是环的入口了。

【力扣每日一题】2023.7.30 环形链表2,力扣每日一题,leetcode,链表,算法,数据结构,c++ 文章来源地址https://www.toymoban.com/news/detail-622604.html

代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==nullptr) return nullptr;
        //快慢指针
        ListNode* fast=head;
        ListNode* slow=head;

        while(fast!=nullptr && fast->next!=nullptr){
            //快指针每次移动两次,慢指针每次移动一次
            slow=slow->next;
            fast=fast->next->next;
            //如果相遇则是有环,开始寻找入口
            if(fast==slow){
                fast=head;
                while(fast!=slow){
                    fast=fast->next;
                    slow=slow->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};

到了这里，关于【力扣每日一题】2023.7.30 环形链表2的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！