网站后端开发软件,cc域名做门户网站,移动应用开发案例,哪有学ui设计培训学校这是链表的第15题#xff0c;力扣链接。 给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。 如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链…这是链表的第15题力扣链接。 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例 1 输入head [3,2,0,-4], pos 1
输出返回索引为 1 的链表节点
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出返回索引为 0 的链表节点
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出返回 null
解释链表中没有环。 这道题是查找链接尾节点的那个节点。上一道题的解法中哈希表还是可以用的因为它是一个一个查重的在第一个节点走第二次的时候就可以弹出了。
func detectCycle(head *ListNode) *ListNode {hashTable : make(map[*ListNode]bool, 0)for head ! nil {if _, ok : hashTable[head]; ok {return head} else {hashTable[head] true}head head.Next}return nil
}
再回看一下那个快慢指针的解法可以解决问题吗其实不一定可以有可能在环形链表中的其他节点两个指针碰上了。
先说结论让两个指针依旧是快慢去跑当两个指针遇到以后快指针回到head然后同步去跑再次遇到的就是入口。
func detectCycle(head *ListNode) *ListNode {if head nil || head.Next nil {return nil}pre, cur : head, headfor cur ! nil cur.Next ! nil {pre pre.Nextcur cur.Next.Nextif pre cur {second : headfor second ! cur {second second.Nextcur cur.Next}return second}}return nil
} 然后说原理快指针式慢指针的两倍两个速度差为一个环。具体分析原理详见大神给的题解。
