传送门

牛客面试必刷101题—— 判断链表中是否有环
牛客面试必刷101题—— 链表中环的入口结点

题目及解析

题目一

代码

package mainimport . "nc_tools"/** type ListNode struct{*   Val int*   Next *ListNode* }*//**** @param head ListNode类* @return bool布尔型*/
func hasCycle(head *ListNode) bool {if head == nil || head.Next == nil {return false}slow := headfast := head.Nextfor slow != fast {if fast == nil || fast.Next == nil {return false}fast = fast.Next.Nextslow = slow.Next}return true
}

题目二

代码

package mainfunc EntryNodeOfLoop(head *ListNode) *ListNode {slow := headfast := headfor fast != nil && fast.Next != nil {slow = slow.Nextfast = fast.Next.Nextif slow == fast {fast = headfor slow != fast {slow = slow.Nextfast = fast.Next}return slow}}return nil
}

总结

今天的解题算法主要使用了双指针这一算法，我们利用定义快慢指针来判断链表中是否有环以及环的节点，这里的理论依据主要是floyd判圈算法，大家有兴趣的化可以看一下文末的文章来理解一下该算法，这里就不做赘述了

拓展

floyd判圈算法