环形链表 leetcode142
该题目要求找到入环的第一个节点
我们可以通过map进行记录，没到新的节点查询是否经过原有节点
入环节点，上两个节点的next相同
若有入环节点，则一定能检测到；若没有，则总会到达最后节点
暴力遍历 map哈希记录
// 暴力遍历 map哈希表记录
func detectCycle(head *ListNode) *ListNode {
dummyHead := &ListNode{
Next: head}
table := map[*ListNode]int{
}
//若不成环，会走出循环
for dummyHead.Next != nil {
if _, ok := table[dummyHead.Next]; ok {
return dummyHead.Next
}
table[dummyHead.Next] = 1
dummyHead = dummyHead.Next
}
return nil
}
时间、空间复杂度都为O（n）
快慢指针法
思路解析
什么如果成环，快指针一定会再慢指针没有转完一圈之前追上满指针？
由于快指针的移动速度为2，慢指针的移动速度为1， 二者相对速度为1
所以当快指针跟在慢指针后面时有以下几种情况- 快指针落后2 -> 快指针落后1 ->重合
- 快指针落后1 ->** 重合**
- 快指针与慢指针重合
所以说只要快指针从后面追上慢指针，一定重合
最极端的情况：刚进入节点时，慢指针此时在相交节点上，快指针在慢指针前面一个
- 我们设到相遇所需的步数为x，环长为n
- 当相遇时，应该两个指针走过的节点数相同
- 快指针由于是转了一圈再追上慢指针，其长度计算前去圈长
- 快指针初始+1，LENfast=2x+1-n
- 慢指针长度LENslow=x
- 二者相同时，2x+1-n=x -> x=n-1
也就是说即使在最极端的情况下也能在慢指针还没走完第一圈，到倒数第一个节点时与快指针相遇
得到二者一定相遇时，我们如何确定到底哪个节点是入环节点？
- 到相遇时，快指针走过的总距离F=a+n(b+c)+b ,n为快指针转过的圈数
- 慢指针走过的距离S=a+b
- 此时S=F,即a+n(b+c)+c=a+b -> a=(n-1)(b+c)+c
- 通过这个方程我们可以看出来初始节点距离相交节点的距离为 n-1圈 圈长加c，而相遇节点距相交节点的距离为c
- 所以从相遇节点和初始节点各出一个指针，总会在慢指针走完n-1圈在走玩c后在相交节点相遇
// 双指针法 快慢指针
func detectCycle(head *ListNode) *ListNode {
fast, slow := head, head
//若有相交节点，则快慢指针一定会相遇
for fast != nil && slow != nil {
slow = slow.Next
//防止fast指针超出链表限制
if fast.Next == nil {
return nil
}
fast = fast.Next.Next
//从相遇节点开始寻找相交节点
if fast == slow {
//题目要求不修改链表
p := head
for p != slow {
slow = slow.Next
p = p.Next
}
return p
}
}
return nil
}
