NOTES · 学习笔记
环形链表 Ⅰ & Ⅱ
题目
环形链表 Ⅰ
我们看示例 1,如何判断一个链表是否有环。我们可以通过循环遍历链表的方式来判断是否有环。
首先,我们需要定义一个 map,用来保存已经访问过的链表节点指针。然后定义一个 curr 指向头节点,通过循环不断遍历链表。
在循环过程中,我们先判断当前 curr 节点是否已经保存在 map 中。如果已经保存过,说明我们再次访问到了同一个节点,那么链表中就存在环,直接返回 true。
如果当前节点还没有被访问过,我们就将它保存到 map 中,然后通过 curr = curr.Next 移动到下一个节点,继续遍历。
如果链表中存在环,那么我们最终一定会再次访问到之前保存过的某个节点,此时就会返回 true。
如果链表没有环,那么 curr 最终会移动到 nil,循环结束,返回 false。
func hasCycle(head *ListNode) bool {
visited := map[*ListNode]bool{} // visiter是已经访问过节点的,用来保存链表节点地址
curr := head // 当前curr指向头节点
for curr != nil {
if visited[curr] {
return true // 我们循环走一遍链表,如果出现相同的链表,说明有环
}
visited[curr] = true
curr = curr.Next // 指向下一个链表
}
return false
}环形链表 Ⅱ
根据上一题的思路,我们再来看看这道题。这道题和上一题的区别在于,一个是判断链表是否有环,一个是找到环的入口节点。
那么我们其实可以继续使用上一题的 map 思路。首先定义一个 map,用来保存已经访问过的链表节点指针,然后定义一个 curr 指向头节点,通过循环不断遍历链表。
在遍历过程中,我们先判断当前 curr 节点是否已经保存在 map 中。如果没有,就将当前节点保存到 map 中,然后通过 curr = curr.Next 移动到下一个节点,继续遍历。
如果链表中存在环,那么当我们遍历到环的入口后,还会继续沿着环前进,最终再次回到之前访问过的节点。因为 map 已经保存了之前访问过的节点,所以当我们再次遇到这个节点时,就能判断出它已经出现过。
而这个第一次被重复访问到的节点,就是环的入口。因此,我们直接返回当前的链表节点指针 curr 就行了。
如果遍历过程中,curr 最终移动到了 nil,说明链表没有环,此时返回 nil。
这里需要注意,map 保存的是节点指针,而不是节点的值。因为不同节点可能存储相同的值,但它们仍然是不同的节点,所以我们需要通过节点指针来判断是否访问过同一个节点。
func detectCycle(head *ListNode) *ListNode {
visited := map[*ListNode]bool{}
curr := head
for curr != nil {
if visited[curr] {
return curr // 返回指针
}
visited[curr] = true
curr = curr.Next
}
return nil
}