Python程序检测链表中的循环

在Python中，我们可以使用一种名为“快慢指针”的算法来检测链表中的循环。这个算法的原理很简单，我们使用两个指针，一个每次移动一个节点，另一个每次移动两个节点。如果链表中存在循环，那么这两个指针最终会相遇。

下面是使用Python实现的代码示例：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head

        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

在上面的代码中，我们定义了一个ListNode类来表示链表节点，其中val表示节点的值，next表示指向下一个节点的指针。然后我们又定义了一个Solution类来实现hasCycle方法，该方法接收一个链表头节点作为参数，并返回一个布尔值表示链表是否存在循环。

在hasCycle方法中，我们使用了两个指针，slow和fast，它们最初都指向链表的头节点。然后我们在一个循环中，每次将slow指针向前移动一个节点，将fast指针向前移动两个节点，直到链表结束或者fast指针指向了一个空节点。如果链表中不存在循环，那么fast指针将先到达链表末尾，while循环将结束并返回False，表示链表中没有循环。如果链表中存在循环，那么fast指针和slow指针最终会相遇，我们就可以通过判断slow和fast是否相等来判断链表中是否存在循环。

接下来，我们使用一个示例来演示如何使用上面的代码来检测链表中的循环。假设我们有一个链表1->2->3->4->5->2，其中数字表示节点的值，箭头表示指向下一个节点的指针。如下图所示：

1 -> 2 -> 3 -> 4 -> 5 -> 2
              ^---------|

在上面的链表中，数字2出现了两次，这意味着链表中存在循环，且循环的起点为数字2所在的节点。我们可以用下面的代码来验证这一点：

if __name__ == '__main__':
    # 创建链表
    n1 = ListNode(1)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n4 = ListNode(4)
    n5 = ListNode(5)

    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    n5.next = n2

    # 检测链表中的循环
    s = Solution()
    print(s.hasCycle(n1))  # True

在上面的代码中，我们首先创建了一个链表，然后将它的最后一个节点的next指针指向了第二个节点，形成了一个循环。然后我们创建了一个Solution对象，调用了它的hasCycle方法，将链表头节点作为参数传入。最后打印出了返回值，预期结果为True，表示链表中存在循环。

更多Python相关文章，请阅读：Python 教程