欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-03 17:54:21
牛客 剑指Offer 单链表判断是否有环 以及找出环的入口点。...

题目:

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

解析:

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

代码:

/*
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