🖊作者 : Djx_hmbb
📘专栏 : 数据结构
😆今日分享 : 霍桑效应(霍索恩效应) : 是指那些意识到自己正在被别人观察的个人具有改变自己行为的倾向。
霍桑效应告诉我们：从旁人的角度，善意的谎言和夸奖真的可以造就一个人；从自我的角度，你认为自己是什么样的人，你就能成为什么样的人。

🖋题目链接：

【力扣-141】 环形链表
【力扣-142】 环形链表 II

✔题目>环形链表 :

🔎代码详情:

bool hasCycle(struct ListNode *head) {
    struct ListNode *fast,*slow;
    fast = slow = head;
    
    //判断是否有环
    while(fast && fast->next){
        fast = fast->next->next;
        slow = slow->next;
        //追击问题
        if(fast == slow){
            return true;
        }
    }
    return false;
}

✔题目>环形链表 II:

✔解题思路：

如果链表存在环，则fast和slow会在环内相遇，定义相遇点到入口点的距离为X,定义环的长度为C,定义头到入口的距离为L,fast在slow进入环之后一圈内追上slow,则会得知：
slow所走的步数为:L + N
fast所走的步数为：L + N + K * C
并且fast所走的步数为slow的两倍，故：
2*(L + N) = L + N + K * C
即： L = K * C - N
所以从相遇点开始slow继续走，让一个指针从头开始走，相遇点即为入口节点

🔎代码详情:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast,*slow;
    fast = slow = head;
    
    //判断是否有环
    while(fast && fast->next){
        fast = fast->next->next;
        slow = slow->next;
        //追击问题
        if(slow == fast){
            struct ListNode *meet = slow;
            struct ListNode *start = head;
            while(meet != start){
                meet = meet->next;
                start = start->next;
            }
            return meet;
        }
    }
    return NULL;
}

总结:

这个题目考察的主要是思维,如果是在搞不懂,也不用太气馁,慢慢来,实在不行,咱记住怎么写的就行,问题不大!

家人们,点个再走呗~