链表中环的入口节点

这是《剑指Offer》的第 23 题：

如果一个链表中包含环，如何找出环的入口节点？

这个题，我首先想到的是，环的入口节点就是在遍历数组的时候第一个被访问两次的节点。 基于这个结论，我们可以定义一个 hash 表，记录每个节点被访问的次数。当遇到一个节点 被访问两次，我们立即把这个节点返回。下面是实现代码：

package main

func EntryNodeOfLoop(pHead *ListNode) {
    hashNode := map[*ListNode]int{}

    for node := pHead; node != nil; node = node->next {
        if _, ok := hashNode[node]; !ok {
            hashNode[node] = 1
            continue
        }
        return node
    }
    return nil
}

因为这个方法需要遍历一次链表，所以它的时间复杂度为 O(n)；又因为我们需要一个和链表一样大的 hash 表， 所以它的空间复杂度也是 O(n)。

有没有空间复杂度为 O(1) 的解法呢？

通过阅读《剑指Offer》中对这道题的解析，我找到了这样一种方法。首先，我们需要判断链表中是否有环。 如果有环，那么我们只需要知道环中节点在数目 n，然后，借用上一题的方法，设置两个指针，后一个指针比 前一个指针多走 n 步，然后我们开始遍历链表，两个指针相遇的节点就是我们要找的节点。

那么如何判断链表中存在环呢？还记得我们如何取一个链表的中间节点的方法吗？用两个指针去遍历链表，一个 一次走一步，另一个一次走两步。当快的指针走到尾节点时，第一个指针所在的位置就是链表的中间节点。其实， 这个方法也可以用来去判断链表中是否存在环。我们还是用两个指针，一个一次走一步，另一个一次走两步。如果 链表中存在环，那么这两个指针一定会在环中相遇。所以，只要在遍历的过程中两个指针相遇了，那么说明 链表中一定存在环。

然后，我们需要知道链表中环的节点数目。上一步，我们有两个指针在环中相遇，那么我们可以让一个指针不动， 另一个指针向前遍历，两个指针再次相遇所经过的节点数就是环中的节点数目 n。

最后，我们只需要再次利用 24 题的方法，定义两个指针，让一个指针先走 n 步，然后再让两个指针向前遍历。 它们相遇的节点就是环开始的节点。值得注意的是，在 24 题中，我们要得到倒数第 k 个节点，我们是让一个 指针向前先走 k - 1 个节点，这里我们则是让指针向前走 n 个，而不是 n - 1。这是为什么呢？因为在 24 题中， 我们的目标是当跑得快的那个指针指向尾结点时，慢一些的那个指针指向倒数第 k 个节点。而这道题中，我们的 目标是让两个指针相遇，所以跑得快的指针要比 24 题的多跑一步，所以是要向前走 n 个节点。

因为这道题 Leetcode 中没有，而牛客网有，所以我在牛客网上提交了代码。

这道题给我的启示如下：

• 用两个指针，一个一步一个节点，另一个一步两个节点，这种方法不仅可以用来找到链表中的中间节点，而且可以用来判断 一个链表中是否含有环
• 在链表的题目中应该灵活运用多个指针遍历链表的技巧，具体问题具体分析，万万不可死记结论。比如这道题的最后一步， 我一开始就是让快一些的节点向前走 n - 1 步，但是却导致了无限循环。仔细分析之后，将 n - 1 改为 n，这才顺利通过 测试。

以上。