【前端面试常见算法题系列】141. 环形链表（简单）-一一网

“Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。”

一、题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
复制代码

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
复制代码

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
复制代码

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

二、思路分析

题目要我们判断链表是否存在环，翻译一下也就是：判断链表是否能走到 NULL 。

小明：噢~我知道了，直接让 head 遍历，如果 head == NULL 就 return false ，否则 return true ，很简单嘛~~
李华：不能吧，如果示例是一个没有环形的链表，确实可以这样。但如果给了一个环形链表，那不是会一直循环下去么，啥时候返回呀？
小明：是啊，那应该用什么办法退出循环呢？遇到 base case 就 return 。
李华：还记得 双指针技巧 吗，我们可以此为切入点。

思路如下：

环形链表就像学校操场上的跑道，双指针就像跑道上的两个人，证明链表环形就相当于证明跑道上的两个人会相遇。
而人与人的跑步速度是不同的，那么在学校跑步比赛时，是不是会有跑得快的人在前方，（假设人的体力无限，速度始终保持不变）跑完一圈后追上了跑得慢的人，那一瞬间两个人就相遇了，这就证明了跑道是圆形的（如果不是圆形的那肯定不会相遇了呀）。
在这个简单的类比举例下，我们就可以开始做这道题了：定义两个指针，快指针 fast ，慢指针 slow ，初始值都为 head ，然后开始遍历，快指针始终比慢指针多走一步，如果 slow == fast 就 return true ，如果不相等就继续遍历嘛。那要遍历到什么时候呢，如果链表真是环形的，自然会有 slow == fast 的时候，如果不是环形的话，就像小明说的那样遇到 NULL 就可以退出循环了，也就 return false 了，因此循环条件便为 fast != NULL && fast -> next != NULL。

如此，这道题就 over 了。完结撒花 ^_^

三、AC 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head, * fast = head;
        while (fast != NULL && fast -> next != NULL) {
            slow = slow -> next;
            fast = fast -> next -> next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};
复制代码