NOTES · 学习笔记

环形链表 Ⅰ & Ⅱ

LeetCode链表 · 简单约 5 分钟

题目

环形链表 Ⅰ

我们看示例 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
}