前言
中间又断更新。
正文
问题来源
本问题来自leetcode上的142题。
问题描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1:
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2:
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3:
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
分析：
用一个map来记录访问过的节点
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
m := make(map[*ListNode]struct{})
for head != nil {
if _, ok := m[head]; ok {
return head
}
m[head] = struct{}{}
head = head.Next
}
return nil
}
假设非环部分的长度是x，从环起点到相遇点的长度是y。环的长度是c。 现在走的慢的那个指针走过的长度肯定是x+n1c+y，走的快的那个指针的速度是走的慢的那个指针速度的两倍。这意味着走的快的那个指针走的长度是2(x+n1c+y)。
还有一个约束就是走的快的那个指针比走的慢的那个指针多走的路程一定是环长度的整数倍。根据上面那个式子可以知道2(x+n1c+y)-x+n1c+y=x+n1c+y=n2c。
所以有x+y=(n2-n1) * c,这意味着什么？我们解读下这个数学公式：非环部分的长度+环起点到相遇点之间的长度就是环的整数倍。这在数据结构上的意义是什么？现在我们知道两个指针都在离环起点距离是y的那个相遇点，而现在x+y是环长度的整数倍，这意味着他们从相遇点再走x距离就刚刚走了很多圈，这意味着他们如果从相遇点再走x就到了起点。 那怎么才能再走x步呢？答：让一个指针从头部开始走，另一个指针从相遇点走，等这两个指针相遇那就走了x步此时就是环的起点。
func detectCycle(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return nil
}
var (
slow = head
fast = head
tortoise *ListNode
)
for slow != nil && fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
tortoise = slow
break
}
}
if tortoise == nil {
return nil
}
for tortoise != head {
tortoise, head = tortoise.Next, head.Next
}
return tortoise
}
总结：
勤思考。
结语
不管怎么样好好加油。
