如何判断一个单链表是否有环

可以使用快慢指针的方法来判断一个单链表是否有环。具体来说，我们可以定义两个指针，一个指针每次向前移动一个节点，另一个指针每次向前移动两个节点。如果存在环，那么快指针最终会追上慢指针，此时就可以判断出链表中存在环。如果快指针到达链表末尾都没有追上慢指针，那么链表中就不存在环。

相关问题

判断单链表是否有环

判断单链表是否有环可以使用快慢指针的方法。

定义两个指针，一个快指针和一个慢指针，初始时均指向链表头部。快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，则快指针最终会追上慢指针，此时链表有环；如果链表不存在环，则快指针会先到达链表尾部，此时链表无环。

以下是该算法的示例代码：

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

def hasCycle(head: ListNode) -> 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

其中，`ListNode` 是单链表节点的定义，`hasCycle` 是判断单链表是否有环的函数。函数中，如果链表为空或只有一个节点，直接返回 False。然后，定义快慢指针，慢指针指向头节点，快指针指向头节点的下一个节点。当快指针追上慢指针时，说明链表有环，返回 True；当快指针到达链表尾部时，说明链表无环，返回 False。

判断带头结点的单链表是否有环

判断一个带头结点的单链表是否存在环，可以使用“快慢指针”（Floyd’s Tortoise and Hare Algorithm 或者 Two Pointer Method）的方法。这种方法涉及两个节点，一个移动得较慢（每次移动一步），另一个移动得较快（每次移动两步）。如果链表有环，那么快指针最终会追上慢指针；如果没有环，快指针会先到达链表的尾部。

步骤如下：
1. 初始化两个指针，分别指向头结点的下一个节点（慢指针）和头结点的第二个节点（快指针）。
2. 循环移动这两个指针，直到它们相遇，或者其中一个指针达到链表的尾部（即为空）。
3. 如果相遇，说明链表中有环；如果到尾部未相遇，则链表无环。

如果你想要实现这个算法，可以考虑用Python编写如下：

def hasCycle(head):
    if not head or not head.next:
        return False
    slow = head.next
    fast = head.next.next
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    return True