如何判断一个链表是否有环？请给出思路和代码。

Question

Accepted Answer

判断链表是否有环可以使用快慢指针的方法。思路是定义两个指针，一个快指针和一个慢指针，慢指针每次移动一步，快指针每次移动两步。如果链表中有环，那么快指针最终会追上慢指针；如果链表中没有环，快指针会先到达链表的末尾。以下是Python代码实现：
python
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

时间复杂度为$O(n)$，因为快指针最多遍历链表两次。空间复杂度为$O(1)$，只使用了常数级的额外空间。