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

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

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

目录

• 带环链表详解：环形链表检测与入环节点查找
• • 一、环形链表II：检测环的存在
  • • 1.1、面试详解
  • 二、环形链表II：定位入环节点

一、环形链表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; // 无环}

力扣提交结果也是没问题的。

或许很多人知道这么做，但是，why，却很少知道，我们来分析一下：


解释完毕。
不理解得可以这样看：

可见，这道题还是对于数学思维的要求。
还有一种做法，我们可以提一下：

相关链接：相交链表，可以试着做一下相交链表，然后用第二种方法来解决这个问题。

如果本文对您有启发：
✅ 点赞 - 让更多人看到这篇硬核技术解析 ！
✅ 收藏 - 实战代码随时复现
✅ 关注 - 获取数据结构系列深度更新
您的每一个[三连]都是我们持续创作的动力！✨