038. 编写一个函数，检查一个链表是否有环

在 Python 中，可以通过使用快慢指针（Floyd 判圈算法）来检查一个链表是否有环。以下是实现这一功能的代码：

示例代码

class ListNode:
    """
    定义链表的节点类。
    """
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def has_cycle(head):
    """
    检查链表是否有环。

    参数:
        head (ListNode): 链表的头节点。

    返回:
        bool: 如果链表有环，返回 True；否则返回 False。
    """
    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  # 如果快指针到达链表末尾，说明没有环

# 测试代码
# 创建一个有环的链表
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # 形成环

# 检查链表是否有环
print("链表是否有环？", has_cycle(node1))  # 输出：True

# 创建一个没有环的链表
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)

node1.next = node2
node2.next = node3

# 检查链表是否有环
print("链表是否有环？", has_cycle(node1))  # 输出：False

代码解释

定义链表节点类：

定义了一个 ListNode 类，表示链表的节点。每个节点包含一个值 value 和一个指向下一个节点的指针 next。

定义函数：

定义了一个名为 has_cycle 的函数，用于检查链表是否有环。

初始化指针：

如果链表为空（head 为 None），直接返回 False。
初始化两个指针 slow 和 fast，都指向链表的头节点。

移动指针：

使用 while 循环，条件是 fast 和 fast.next 都不为 None。
在每次循环中，slow 指针移动一步，fast 指针移动两步。

检查是否相遇：

如果 slow 和 fast 指针相遇（slow == fast），说明链表有环，返回 True。
如果 fast 指针到达链表末尾（fast 或 fast.next 为 None），说明链表没有环，返回 False。

测试结果

运行上述代码后，输出如下：

链表是否有环？ True
链表是否有环？ False

注意事项

快慢指针法：快慢指针法是一种常见的检测链表是否有环的方法。如果链表有环，快指针最终会追上慢指针；如果链表没有环，快指针会先到达链表末尾。
边界条件：在实现时需要注意边界条件的处理，例如链表为空或只有一个节点的情况。
效率：快慢指针法的时间复杂度为 O(n)，其中 n 是链表的长度。这种方法不需要额外的存储空间，空间复杂度为 O(1)。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)