python判断链表是否有环的实例代码

题目描述：给定一个链表，判断链表是否有环。

思路分析

这个问题可以使用快慢指针解决。两个指针同时从头开始，一个每次走一步，一个每次走两步。如果链表上有环，那么这两个指针最终一定会相遇。如果指针走到 None 了，那么就说明不存在环。

代码实现

以下是Python实现的代码：

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

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False
        slow = head
        fast = head.next
        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

示例说明

例如，给定以下链表：

a -> b -> c -> d -> e -> c

其中，c 和 e 是相同的节点，构成环。代码运行结果为 True。

再例如，给定以下链表：

a -> b -> c -> d -> e

其中，不存在环。代码运行结果为 False。