带环链表详解：环形链表检测与入环节点查找-EW帮帮网

请添加图片描述

带环链表详解：环形链表检测与入环节点查找

✨前言：带环链表是数据结构中的经典问题，涉及链表操作与数学推理的巧妙结合。本文将深入解析环形链表的检测原理和入环节点的定位方法，通过快慢指针的数学证明与可视化分析，揭示算法背后的精妙设计。无论是面试准备还是算法学习，这些内容都将为你提供扎实的理论基础和实践指导。
📖专栏：数据结构与算法

一、环形链表II：检测环的存在

题目描述：

原题链接：《环形链表》

对于这一题，我们就要用到快慢指针的思路。
首先先看一下快慢指针的概念：使用两个移动速度不同的指针在数组或链表等序列结构上移动。
具体怎么实践呢，我们来看图分析：

在上面我们分析了链表带环的情况下的处理方式，很明显，需要写个循环

bool hasCycle(struct ListNode* head)
{
    struct ListNode* slow = head, * fast = head;
    while ( )//?
    {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast)
            return true;
    }
    return false;
}

那循环条件是什么呢，这个时候，我们就要思考，我们只考虑了链表为带环的情况，而并没有考虑了链表不带环的情况。
那链表不带环的话，按照这种方法执行下去，就成了找单链表的中间节点了。此时，循环条件就为fast && fast->next

没有做过【链表的中间节点】也可以先做一下，这篇博客的重点不在这。有什么问题可以私信交流。
故最终的代码为：

bool hasCycle(struct ListNode* head)
{
    struct ListNode* slow = head, * fast = head;
    while (fast && fast->next)//如果不是带环链表，则退出循环
    {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast)
            return true;
    }
    return false;
}

如果还是不能理解，可以这样想，对于此链表来说，只有两种情况：是否为带环链表，
如果是，两个指针最终会相遇；
如果不是，fast指针会为空（链表节点奇数个）或者fast->next为空（链表节点为偶数个）。

上面我们说到的都比较简单，理解起来也较为容易，但是，在面试的时候不会这么简单的，下面我们就来讲讲我们在面试中会遇到的情况。

1.1、面试详解

作为面试官，会这样问：（重点）

1. 上面的情况为什么一定会相遇，有没有可能会错过，永远追不上？请证明；
2. slow一次走1步，fast走3步、4步、5步、n步，一定能追上吗？请证明。

我们一个一个看，先来看为什么在slow走一步，fast走两步的时候一定会相遇。

证明成功。

那对于slow一次走1步，fast走3步、4步、5步、n步，一定能追上吗？

假设slow一次走1步，fast走3步：

下一轮追击开始

即

在这里，只有一种情况追不到，N为奇数，C为偶数，那这种情况存在吗，我们来看看，

现在我们就对化简出来的这个式子进行分析

那以我们上面的N为奇数，C为偶数的情况带入之后：

故N为奇数，C为偶数的情况不会出现，
我们回归源头，所以在slow一次走1步，fast走3步的时候一定会相遇。
在fast走其它步可自行证明。
可见，此题主要考察对数学的要求，以及我们对于一个问题要探究到底。

二、环形链表II：定位入环节点

题目描述：

原题链接：《环形链表2》
会发现，比上一个题就多了一个返回链表入环的第一个节点。
那该怎么办呢？我直接告诉大家怎么做吧：

代码：

struct ListNode* detectCycle(struct ListNode* head) 
{
    struct ListNode *slow = head, *fast = head, *cur = head;
    // 先判断是否有环
    while (fast && fast->next) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) // 有环
        {
            while (slow != cur) 
            {
                slow = slow->next;
                cur = cur->next;
            }
            return cur;
        }
    }
    return NULL; // 无环
}