我将使用我值得信赖的编程语言 Python 记录我通过 Sean Prashed 出色的 LeetCode Patterns (https://seanprashad.com/leetcode-patterns/) 从易到难的旅程。今天我们将解决 LeetCode 的链表循环 (https://leetcode.com/problems/linked-list-cycle/) 问题。与往常一样,这是a 解决方案而不是the 解决方案。编程的美妙之处在于有许多方法可以达到相同的结果。

任务:给定 ***head***,链表的头部,判断链表中是否有环。

链表中有一个循环,如果链表中存在可以通过连续跟随 ***next*** 指针再次到达的节点。在内部, ***pos*** 用于表示tail的 ***next*** 指针所连接的节点的索引。请注意 ***pos*** *** 不作为参数传递。***

返回 ***true*** 如果链表中存在循环。否则,返回 ***false***.

我将展示这个问题的两种不同解决方案:一种使用字典,另一种使用“兔子和乌龟”方法。

运行时复杂度:O(n)

空间复杂度:O(n)

字典方法的 LeetCode 性能这背后的想法是每当我们遇到一个节点时,我们根据它的值作为键对其进行散列。字典值将存储为节点数组,因为可以有多个具有相同值的节点。我们使用这个字典来跟踪我们遇到的节点,如果遇到我们以前见过的节点,我们返回 true。如果我们不这样做,我们就结束了,就没有循环,我们返回 false。

由于散列的性质,该算法速度很快,但确实占用了大量空间。我们可能无法拥有比线性时间更好的运行时复杂度,但是我们可以拥有更好的空间复杂度吗?

Hare and Tortoise 解决方案代码运行时复杂度:O(n)

空间复杂度:O(1)

兔子和乌龟方法 LeetCode 表演在伊索寓言兔子和乌龟中,兔子和乌龟互相赛跑。兔子看到乌龟远远落后,决定小睡一会儿,乌龟永不放弃。虽然上述算法的灵感来自寓言,但没有乌龟赢的例子,只有平局。

野兔(我将它命名为兔子以使事情变得混乱)从不休息。野兔一次跳过两个节点,而乌龟(我将其命名为乌龟,使事情变得更加混乱)通过链表一次在一个节点上移动。如果链表没有环,兔子会获胜,因为它比乌龟移动得快得多。在这种情况下,我们中断 while 循环并返回 false。如果链表有一个循环,兔子会继续在循环中跳跃,直到乌龟最终赶上兔子。一旦他们降落在同一个节点,他们就会意识到他们都被骗了,结果是平局。然后我们返回 true,因为我们现在可以确认链表有一个循环。

我们可以观察到字典方法和 Hare 和 Tortoise 方法都具有线性时间复杂度,但是 Hare 和 Tortoise 比字典方法具有更好的空间复杂度。这表明虽然哈希表在提高运行时复杂性方面非常出色,但有时可以使用替代方法以更少的空间实现相同的结果。