leetcode 141.环形链表

可以更新一下最近做的链表题了，也算是做最近的一个知识总结（如果更新 leetcode题目，下一题是对这道题的一个提升，还有今天提到的 878.链表的中间节点 ，相关博客我还没出，等我后面去更新啊，对于快慢指针不是很了解的，听懂今天的思路即可）

141.环形链表

题目

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

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

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

题目链接

力扣（LeetCode）官网 – 全球极客挚爱的技术成长平台

文字 和 画图 分析

大概是这样一个链表：

其中：val 存放数值，next存放 下一个节点的地址

这道题我们用快慢指针的思想去做：

定义一个 fast指针 和 slow指针 接收第一个节点的地址

fast指针 每次都比 slow指针 多走一步

这里只有两种情况：

第一个是它没有环形链表

第二个是它有环形链表

如果是第一种情况，那么就会遇到 fast 为空指针 或者 fast->next 为空指针（不知道的看 878.链表的中间节点）的情况，以这个为循环条件，就会跳出循环，我们由此知道它没有环形链表

如果是第二种情况，那么循环就不会退出，当 slow指针 进入环形链表的第一个节点时，它与 fast指针差距 N个距离，但是 fast指针 每次都比 slow指针 多走一步，每次它们之间的距离就会减小 1，直到距离为 0 ，它们最后相遇了，成功判断它有环形链表

代码

bool hasCycle(struct ListNode *head) 
{
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    if(head == NULL || head->next == NULL)
    {
        return false;
    }
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}

提问：

两个指针每次相差的步数一定得是 1 吗？

回答：必须是

为什么呢？

回答：如果确定是环形链表，结束这个循环的条件跟 环形链表的长度和每次两个指针移动步数之差 有关，举个例子，如果两个指针每次相差 2 步，若 slow指针 刚进入环中与 fast指针差距  N 个距离，它们之间的距离由 N 变成 N – 2，N – 4，若 N 为偶数，可以两个指针的距离可以为 0 ,若 N 为奇数，则 fast指针 会错过 slow指针，开始下一轮的追击，距离变成 C – 1（C为这个环形链表的长度），若 C – 1 不是 2 的倍数，说明这一回合 fast指针 依旧会错过 slow指针，并且以后都会错过 slow指针，循环无法结束

代码007普通

打赏 收藏 海报 链接