LeetCode，给定一个链表，判断链表中是否有环
力扣题目：
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。
- 来源：力扣（LeetCode）
- 链接：https://leetcode-cn.com/problems/linked-list-cycle
解题
1. 哈希表
我们最容易想到的方法就是使用一个哈希表来存储所有节点。遍历所有节点，判断当前节点有没有存在哈希表中，如果存在过说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。
func hasCycle(head *ListNode) bool {
maps := map[*ListNode]struct{}{}
for head != nil {
if _,ok := maps[head.Next]; ok {
return true
}else{
maps[head.Next] = struct{}{}
}
head = head.Next
}
return false
}
2. 「Floyd 判圈算法」（又称龟兔赛跑算法）
我们还可以使用龟兔赛跑算法，即定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
slow := head
fast := head.Next
for fast != slow {
if fast == nil || fast.Next == nil {
return false
}
slow = slow.Next
fast = fast.Next.Next
}
return true
}
有什么问题，可以公众号内回复或加我微信交流。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-08-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
