海南第六建设工程有限公司网站,wordpress 问答模块,体育馆网站建设,教育类网站建设文章目录 环形链表 leetcode142暴力遍历 map哈希记录快慢指针法 环形链表 leetcode142
该题目要求找到入环的第一个节点 我们可以通过map进行记录#xff0c;没到新的节点查询是否经过原有节点 入环节点#xff0c;上两个节点的next相同 若有入环节点#xff0c;则一定能检… 文章目录 环形链表 leetcode142暴力遍历 map哈希记录快慢指针法 环形链表 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] 1dummyHead dummyHead.Next}return nil
}
时间、空间复杂度都为On
快慢指针法
思路解析 什么如果成环快指针一定会再慢指针没有转完一圈之前追上满指针 由于快指针的移动速度为2慢指针的移动速度为1 二者相对速度为1 所以当快指针跟在慢指针后面时有以下几种情况 快指针落后2 - 快指针落后1 -重合快指针落后1 -** 重合**快指针与慢指针重合 所以说只要快指针从后面追上慢指针一定重合 最极端的情况刚进入节点时慢指针此时在相交节点上快指针在慢指针前面一个 我们设到相遇所需的步数为x环长为n当相遇时应该两个指针走过的节点数相同快指针由于是转了一圈再追上慢指针其长度计算前去圈长快指针初始1LENfast2x1-n慢指针长度LENslowx二者相同时2x1-nx - xn-1 也就是说即使在最极端的情况下也能在慢指针还没走完第一圈到倒数第一个节点时与快指针相遇 得到二者一定相遇时我们如何确定到底哪个节点是入环节点 到相遇时快指针走过的总距离Fan(bc)b ,n为快指针转过的圈数慢指针走过的距离Sab此时SF,即an(bc)cab - a(n-1)(bc)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
}
