力扣 141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
方案一：快慢指针，龟兔赛跑问题，龟每次走一个节点，兔每次走两个节点，如果两者相遇，则构成环。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
// 定义快慢指针
slow, fast := head, head
// 边界判断
for fast != nil && fast.Next != nil {
// 快指针每次走两步，慢指针每次走一步
slow, fast = slow.Next, fast.Next.Next
// 如果相遇则构成环
if slow == fast {
return true
}
}
return false
}
- 时间复杂度：O(n)，因为需要遍历链表中所有元素才能判断是否有环，所以时间复杂度为 O(n)。
- 空间复杂度：O(1)，因为使用了常数量个变量用作辅助计算，所以空间复杂度为 O(1)。