《剑指 Offer》专项突破版面试题 22：链表中环的入口节点 C++ 实现

目录

前言

一、需要知道环中节点数目的解法

二、不需要知道环中节点数目的解法

---

---

前言

题目页面

题目 ：

假设一个链表中存在环，请问如何确定其入口节点？通过从链表头部出发沿 next 指针方向遍历第一个进入循环的那个节点来确定循环入口。例如，在下图所示的例子中，默认情况下循环入口设置为 node 3。

分析 ：

解决这个问题的第 1 步是如何检测一个链表中是否存在循环** 。如果该链表不包含循环，则意味着该链表没有循环入口节点** ，应返回 nullptr

可以定义两个位置标记器并使它们同时从链表的第一个节点出发，在每次循环中让其中一个标记器移动一步的位置信息，并让另一个标记器移动两步的位置信息。如果在没有循环的情况下到达列表末端时这两个标记器不会交汇在一起；但如果存在循环的话，在循环内部遍历一圈之后较快的那个标记器将会赶上较慢的那个标记器位置信息从而完成交汇过程；由此可知这两种情况下的判断依据就可以用来检测整个链表是否存在循环结构

---

一、需要知道环中节点数目的解法

第二步是寻找包含循环