leetcode-141 判断链表是否有环

题目描述

判断给定的链表中是否有环

解题思路

1、借助哈希表

我们可以通过检测某个节点之前是否有访问记录来判定该链表是否存在循环结构。一种常见的技术手段是在遍历时记录已访问过的节点。

我们依次访问每个节点并在哈希表结构中记录它们的引用信息。当遇到空指针null时（即后续没有节点的情况），说明已经完整遍历了整个列表，并且该列表不具备环形特性。若在遍历过程中发现某个节点已经被记录在哈希表中，则判定该列表为具有环形连接特征的循环列表。

2、双指针法

想象一下，两名运动员以不同的速度在环形赛道上跑步会发生什么？

通过引入两个以不同速度运行的快慢指针来完成对链表的遍历操作会显著减少所需的空间资源从而降低了空间复杂度至 O(1)。其中缓慢的慢指针每步仅前进一个节点位置而快速的快指针则每次跨越两个节点。

当列表中没有环时，在快指针遍历至末尾后（即fast pointer最终会先到达列表末端），我们应返回 false。

假设我们有一个环形链表，并将这两个虚拟角色比喻为赛道上的选手——循行者与冲刺者。由于其速度优势，在绕圈的过程中它们必定会相遇。那么背后的原因是什么呢？让我们深入探讨一种特定情形（标记为情况A）。假如冲行着仅落后循行着一步，在下一阶段移动之后，则冲行着各自完成了一次移动任务，并在此时碰头。

除此之外还有什么情况需要考虑吗？例如，在这种