当前位置： 移动技术网 > IT编程>数据库>Mysql > 牛客 剑指Offer 单链表判断是否有环 以及找出环的入口点

牛客 剑指Offer 单链表判断是否有环 以及找出环的入口点

2020年07月15日  | 移动技术网IT编程  | 我要评论

题目：

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解析：

在这里插入图片描述

代码：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode*slow=pHead;
        ListNode*fast=pHead;
        while(fast!=NULL&&fast->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast){
                fast=pHead;
                while(slow!=fast){
                    slow=slow->next;
                    fast=fast->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

基本思路：

\qquad我的解析里面写的还是比较清楚的。这里简单说明一下。解析里面数学证明了如果有环的话，快慢指针一定会相遇的。后面还证明了在相遇之后，把fast指针拿到链表头，slow从相遇点向后移动，现在，二者都是每次移动一个位置。二者的初次相遇点就是链表的环的入口。

谢谢阅读！

本文地址：https://blog.csdn.net/weixin_40007143/article/details/107297812

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网