环形链表

题目 环形链表

image-44eccbda

思路分析

就像是操场跑步 如果存在环 那么只要一直跑下去的话 快的一定会追到慢的 即相遇

拿两个指针 一个slow速度为1 一个fast速度为2

以fast为参照物 则可以认为slow是静止的 fast在以1的速度追赶slow

所以只需要不停地走

当两个相遇的话 就说明存在环

而如果不存在环的话 fast指针一定会先走到那个nullptr处

代码实现

class Solution {

public:

    bool hasCycle(ListNode *head) {

        ListNode *fast = head;

        ListNode *slow = head;

        while(fast != NULL && fast ->next != NULL)

        {

            fast = fast->next->next;

            slow = slow->next;

            if(fast == slow)

                return true;

        }

        return false;

    }

};

同类题型

视频讲解

⬅️ 快慢指针 🏠 00-刷题理模型 ➡️ 环形链表2