力扣 142. 环形链表 II
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
方案一：快慢指针，龟兔赛跑问题，龟每次走一个节点，兔每次走两个节点，如果两者相遇，则构成环。
然后慢指针和原头节点都一次走一步，相遇点便是入环点 （数学问题）。
2 * (l + p) = l + p + k * r ==> l = kr - p = (k - 1) * r + (r - p) ==> l = r - p
l 是头节点到入环点的距离；p 是入环点到相遇点的距离；k 是绕圈数 ；r 是环周长。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
// 定义快慢指针
slow, fast := head, head
// 边界判断
for fast != nil && fast.Next != nil {
// 快指针一次走两步，慢指针一次走一步
slow, fast = slow.Next, fast.Next.Next
// 如果相遇，则表示有环
if slow == fast {
// 慢指针一次走一步，再定一个一个指针从头开始，一次走一步，相遇点便是入环点
for slow != head {
slow, head = slow.Next, head.Next
}
return head
}
}
return nil
}
- 时间复杂度：O(n)，因为需要遍历链表中所有元素才能判断是否有环，并且判断有环后，为了找到入环点行进的距离不超过 n，所以时间复杂度为 O(n)。
- 空间复杂度：O(1)，因为使用了常数量个变量用作辅助计算，所以空间复杂度为 O(1)。