判断链表是否有回环

来源：go-interview / Case

判断链表是否有环，经典的算法是**“快慢指针”（Floyd 判圈算法）**，其基本思想是通过两个指针遍历链表，一个快指针一次走两步，一个慢指针一次走一步。如果链表有环，两个指针最终会相遇；如果没有环，快指针会在链表末尾遇到 null。

Golang 实现代码：

type ListNode struct {
    Val  int
    Next *ListNode
}
 
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
 
    slow, fast := head, head.Next
 
    for fast != nil && fast.Next != nil {
        if slow == fast {
            return true
        }
        slow = slow.Next         // 慢指针走一步
        fast = fast.Next.Next    // 快指针走两步
    }
 
    return false
}

解释：

1. 初始化指针：
   • slow 指针每次走一步，fast 指针每次走两步。
2. 循环条件：
   • 循环条件为 fast != nil && fast.Next != nil，保证快指针没有走到链表末尾。若到达链表末尾说明无环。
3. 相遇判断：
   • 如果 slow == fast，说明链表有环，两个指针在环中某处相遇。
4. 返回值：
   • 如果两个指针相遇，则返回 true；否则，当快指针到达链表末尾时，返回 false。

时间复杂度与空间复杂度：

• 时间复杂度：O(n)，因为慢指针最多遍历整个链表一次，快指针也是如此。
• 空间复杂度：O(1)，只使用了常量空间。

这是链表环检测的高效方法，既不需要额外的存储空间，又能够在线性时间内完成。