链表-如何快速找出一个环形链表入环处，O(1)空间复杂度能否？
问题
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。
示例1
输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。
示例二
输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。
解法一
我们看到在这个链表的末尾连接的下一个节点是链表上的随机一个点，形成一个环形链表，创建一个map,遍历这个链表，key是这个链表的节点，每次map进行put时，判断是否存在，如果存在，说明遇到重复的了，则此时这个节点就是入环处
type ListNode struct {
Val int
Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
if head == nil{
return nil
}
temp1 := head
result := head
//注意map的key不再是指针类型，而是结构体类型
m := make(map[ListNode]int)
for temp1 != nil{
// 通过*取指针变量存储的地址值
current := *temp1
if _,ok := m[current];ok{
result = temp1
break
}else{
m[current] = 1
}
temp1 = temp1.Next
fmt.Println(temp1)
if temp1 == nil{
return nil
}
}
return result
}解法二
上面的方法是利用一个map，在遍历链表的时候，不断往里面放入当前节点，直到发现有key冲突，则终止，返回当前节点就是入环处，空间复杂度为O(n),那有更好的方法吗？O(1)的空间复杂度呢？说一个新的方法，我们声明两个临时指针变量，one,two，one变量在遍历链表时每次都指向下一个节点，two则指向下一个节点的下一个节点，当one和two相遇时，two就已经走了one的两倍的长度了，此时我们声明一个临时指针变量temp,从头部开始遍历，每此遍历都指向下一个节点，one同样，当temp和one相遇时，则这个节点就是入环处，这是什么原理呢？看下图
这个时候我们temp距离1节点处走两步，one节点距离1节点处也是走两步，为什么这么巧呢？我们知道two走的路是one走的路的两倍，也就是现在说two不动，one还需要走同样的路才能再次和two相遇，这个同样的路也就是temp到one当前节点需要走的路，因为这也是one之前走过的路，他们有一个共同的交点就是入环处，代码如下：
type ListNode struct {
Val int
Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
if head == nil{
return nil
}
//两个快慢指针变量
one,two := head,head
for two != nil{
next := two.Next
//说明不存在环形链表
if next == nil || next.Netx{
return nil
}
one = one .Next
two = next.Next
//相遇时终止
if one == two {
break;
}
}
temp := head
//相遇时终止
for temp != one{
temp = temp.Next
one = one.Next
}
return temp
}欢迎大家关注微信公众号：“golang那点事”，更多精彩期待你的到来
腾讯云开发者
