人间算法题：这究竟是不是一个环形的谜题？
摘要：很多人都说人生就是一个循环，每天重复重复。 而所谓环，对于写代码的小伙伴来说是有特殊定义的。我的理解就是节点循环，就成了环。 刚好刷到一个掘金好友分享的腾讯一面算法题：判断一个单链表是不是一个环。 其实有很多办法来实现，但是我更喜欢用快慢指
很多人都说人生就是一个循环，每天重复重复。
而所谓环，对于写代码的小伙伴来说是有特殊定义的。我的理解就是节点循环，就成了环。
刚好刷到一个掘金好友分享的腾讯一面算法题：判断一个单链表是不是一个环。
其实有很多办法来实现，但是我更喜欢用快慢指针来判断环的形成。思路如下：
定义一个slow指针，指向单链表的头部节点head。定义一个fast指针，初始化为head.next。
2.然后先判断fast和fast.next是否是空，如果为空，肯定不是环。
3.然后开始移动快慢两个指针。slow指针每次只移动一个节点，fast指针每次移动2个节点。
4.如果在移动的过程中slow指向的节点等于fast指向的节点，那么说明循环了，这是一个环。
5.如果移动到链表最后（假设不是环，有尾部）还是没有slow和fast节点重合，那么说明不是环。
所谓环，那么就一定会快慢指针一定会相遇。
那么用golang实现一下：
package main
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func HasCircle(head *ListNode) bool {
slow, fast := head, head.Next
if fast == nil || fast.Next == nil {
return false
}
for fast != nil && fast.Next != nil {
if slow == fast {
return true
}
slow = slow.Next
fast = fast.Next.Next
}
return false
}
func main() {
// create the list
head := &ListNode{Val: 1}
head.Next = &ListNode{Val: 2}
head.Next.Next = &ListNode{Val: 3}
head.Next.Next.Next = &ListNode{Val: 4}
head.Next.Next.Next = head.Next
fmt.Println("Is circle? ", HasCircle(head))
}
死去的记忆又在攻击我了，我想起多年前去一家互联网医疗公司面试的时候也遇到这道题，我也给出了这个解法，但是面试官一脸懵逼，无法理解我的思路。今天我仔细想想，也许是他想看到我用深度优先搜索（DFS）来实现。
所谓深度优先，就是一种递归算法，用于搜索图或树数据结构的所有顶点。该算法从起始节点开始，尽可能沿着每条路径探索，直到无法再前进为止，然后进行回溯。DFS通常使用堆栈来跟踪已发现的节点，以便进行回溯。这种算法的时间复杂度为O(V+E)，其中V是顶点数，E是边数。在实际应用中，DFS还有许多应用，包括寻找连通分量、检测图中的环、拓扑排序等。