检查给定链表是否为循环链表

在本教程中，我们将编写 Python 程序来检查给定的链表是否为循环链表。我们将了解确定循环链表的各种高效方法。假定您熟悉链表和循环链表的基本概念（可以跳过介绍部分）。如果您不熟悉链表，让我们简要回顾一下链表。

什么是链表？

链表是一种线性数据结构，它存储下一个元素的地址。每个元素称为节点，节点包含数据和下一个元素的内存地址。我们可以通过指针访问链表中的元素，第一个节点称为头节点。

与数组相比，链表具有优势，因为它动态地存储元素，而数组的大小是固定的。在链表中，我们可以轻松地插入和删除元素。

循环链表

循环链表是一种链表，其中最后一个指针字段指向列表中的一个元素。另一方面，前一个元素的下一个指针字段值为null。当我们遍历整个链表而没有到达 NULL 时，链表中就存在一个循环。

如何检查给定的链表是否为循环链表？

根据两种链表的定义，我们在遍历链表时可以轻松找出。

• 如果没有节点指向 null。
• 如果链表中的任何节点指向头节点或起始节点，则该链表是循环的。

让我们来理解一下解决方案。

解决方案 - 1

按照以下步骤检查给定的链表是否为循环链表。

1. 遍历整个链表。
2. 检查节点是否指向头节点。
3. 如果返回 true，则表示给定的链表是循环的。

让我们来理解下面的代码。

示例 -

输出

The given linked list is not a circular list
The given linked list is a circular list

解释 -

在上面的代码中，我们创建了一个 Node 类来初始化链表的节点。然后我们创建了一个 LinkedList 类，它将指向链表的头节点；最初，它是 None。最后，我们定义了 CircularList 函数，该函数确定给定的链表是否为循环链表。

在此函数中，我们检查 head 是否等于 None。如果为 True，则返回 True。如果 head 不为 None，则将 head 的下一个元素赋值给 current，并将 i 初始化为零。然后我们定义了一个 while 循环，该循环将一直运行，直到 current 不为 None 且 current 不为 head。如果循环终止条件成立，则返回 current 是否等于 head。

解决方案 - 2：双指针解决方案

我们可以使用两个具有不同速度的指针来确定给定的链表是否为循环链表。我们定义一个 slow 指针和一个 fast 指针。我们使用这些指针来遍历链表。慢指针一次移动一步，快指针一次移动两步。

如果链表不是循环的，则快指针将到达下一个指针为 null 的元素的末尾。

让我们来理解一下这个方法。

• 检查 head 是否为 null，返回 false。
• 如果不是，则创建两个指针 slow 和 fast => slow=head, fast = head.next。
• 运行一个循环，直到 slow 不等于 fast。
• 在循环内部，如果 fast 为 null 或 next 为 null，则返回 false。
• 否则，赋值 => slow = slow.next, fast = fast.next.next。
• 返回 true。

让我们将上述方法实现到 Python 代码中。

示例 -

输出

The Given list is a circular list

解释 -

我们在上面的代码中创建了 Node 和 LinkedList 类来初始化节点和 head。然后我们创建了 circular_list() 函数，该函数接受 head 作为参数。如果 head 为 None，则链表不存在；否则，我们将慢指针赋值为 head，将快指针赋值为 head 的下一个元素。然后迭代链表，直到 slow 不等于 fast。在循环中，我们检查 fast 指针是否为 None 或 fast 的下一个元素是否为 None；如果条件为 true，我们返回链表不是循环链表。否则，我们将 slow.next 元素赋值给慢指针，并将 fast.next.next 元素赋值给快指针。如果慢指针和快指针相等，则表示给定的链表是循环链表。循环结束，返回 true 表示循环链表。

双指针解决方案的复杂度分析

如果链表没有循环，快指针将到达末尾。因此，在这种情况下，时间复杂度为 O (n)。如果链表有循环，我们需要计算快指针追赶慢指针所需的步数。让我们来理解两个指针的移动。

慢指针需要 K 步才能进入循环，此时快指针已经在循环中，并且距离慢指针在链表方向上有一个元素。

总运行时间将为 0 (K+D)，其中 K 是从 head 到循环起始元素之间的元素数量。D 代表慢指针到达循环时两个指针之间的距离。空间复杂度为 O (1)。

结论

在本教程中，我们学习了如何检查链表是否为循环链表。我们讨论了两种解决方案，第一种是暴力方法，第二种是双指针方法。双指针方法易于实现，而且效率更高。