Python程序检测链表中的循环

1. 什么是链表循环

在开始讨论 Python程序检测链表中的循环之前，我们先来说一下链表循环的概念。链表循环是指链表中某个节点指向链表中已经出现过的另一个节点，形成一个环的情况。例如下图所示：

2. Python程序检测链表中的循环的实现思路

检测链表中的循环有多种实现思路，下面我们介绍一种较为简单的思路。

2.1 快慢指针法

快慢指针法是检测链表中是否存在循环的一种方法。该方法的基本思路是：设置两个指针（一个快指针和一个慢指针），快指针每次向前移动两个节点，慢指针每次向前移动一个节点。如果链表中不存在循环，则快指针会先到达链表末尾；如果链表中存在循环，则快指针会在某一时刻与慢指针相遇。

具体实现代码如下：

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
def has_cycle(head: Node) -> bool:
    """
    判断链表是否有循环
    :param head: 链表头节点
    :return: boolean
    """
    if not head:
        return False
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

在上面这段代码中，我们定义了一个有两个属性的类 Node，属性 val 代表链表中的值，属性 next 代表链表中的下一个节点。接着我们定义了一个函数 has_cycle，该函数用于判断链表是否有循环。其实现思路就是上文所提到的快慢指针法。需要注意的是，如果链表为空，则认为链表不存在循环。

3. 测试实例

我们来测试一下上面的 Python程序检测链表中的循环的实现：

n1 = Node(3)
n2 = Node(2)
n3 = Node(0)
n4 = Node(-4)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n2
print(has_cycle(n1)) # True

在上面的测试实例中，我们创建了一个环形链表，并使用上面实现的 has_cycle 函数进行判断，得到的结果为 True，证明函数判断的正确性。

4. 总结

本文介绍了 Python程序检测链表中的循环的实现思路，主要是快慢指针法，并给出了测试实例。需要注意的是，在实现时要注意链表为空的情况，不然会导致程序出错。