【LeetCode】环形链表

一时失言乱红尘 2023-07-04 03:27 56阅读 0赞

## 题目描述 ##

给定一个链表，判断链表中是否有环。  
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。  
**示例1：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]  
**示例2：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 1]  
**示例3：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 2]

## 解题思路 ##

设置快、慢两个指针，慢指针走一步，快指针走两步。如果链表中不存在环，快指针最终会走到尾部，此时返回false；若链表中存在环，快指针最终会追上慢指针。

## 完整代码 ##

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    bool hasCycle(struct ListNode *head) { 
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        while(fast && fast->next)
        { 
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
            { 
                return true;
            }
        }
        return false;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020020718455323.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020020718463553.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200207184714768.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1pEXzAxMg==,size_16,color_FFFFFF,t_70