链表登堂入室，经典的微软面试题，你能做出来吗？

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天我们来看一道非常非常经典的算法题，它曾经是微软的著名面试题之一，也是《编程之美》一书中的经典例题。它同样也被收录进了LeetCode当中。

环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

分析

如果只是为了通过，这题其实很简单，我们只需要使用一个数据结构存储下所有遍历经过的节点。只要遇到了之前出现过的节点，那么就返回，否则则继续遍历，直到遍历结束为止。

最坏的情况当中，我们需要额外将链表中的数据都再存储一遍，因此消耗的空间复杂度是

。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> st;
        auto pt = head;

        while (pt != nullptr) {
            if (st.count(pt)) return pt;
            st.insert(pt);
            pt = pt->next;
        }
        
        return nullptr;
    }
};

显然，仅仅是这样的难度是进不了微软的面试题库的。所以我们还要更进一步，加大难度：如果将空间复杂度限制在

呢？

快慢指针

老实说，在没有额外信息的前提下想要直接一步到位想出正解是比较困难的。可能很多算法老手也不一定能马上反应过来。

所以这里我们先退一步，稍微降低一点难度。相信大家也注意到了，本题的名字是环形链表II。自然也有环形链表I，环形链表I的题面和本题完全一样。只不过我们不需要返回环的起始位置，只需要判断是否有环存在。我们可以先想出在

空间复杂度下判断是否有环的方法，再进一步构思出如何找到环开头的位置，这样相对来说会更加自然。

只能使用

的空间复杂度意味着我们不能再记录每一个遍历过的节点，而需要使用其他的方法来判断。我们可以从有环的链表与无环链表的差异来入手。

比较容易想到，如果链表有环的话，那么当我们遍历它的时候会陷入无限循环。但是由于我们事先并不知道链表中节点的个数，所以也就没办法直接根据遍历的节点的个数来判断是否陷入了无限循环。

我们可以用一个非常巧妙的思路来解决这个问题，我们可以把链表中的环想象成学校的操场，遍历节点的指针想象成跑步的学生。如果我们只有一个学生很难判断，但如果我们有两个学生呢？一个跑得快一个跑得慢，那么只要他们一直跑下去，他们一定会某一刻相遇。反之，如果不存在环，他们也就没办法相遇。

我们从这点入手，创建两个指针，一个指针每次移动两个节点，一个指针每次移动一个。如果中途快的指针和慢的指针相等， 那么说明链表中一定有环，快的指针开始跑圈了。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto fast = head, slow = head;
        while (fast != nullptr) {
            fast = fast->next;
            if (fast == nullptr) return false;
            fast = fast->next;
            slow = slow->next;
            if (fast == slow) return true;
        }
        return false;
    }
};

解决了判断是否有环的问题之后，剩下的就是判断环起始的位置了。

怎么判断呢？干想肯定是没用的，我们还是要结合问题来分析。我们用一张图画一下快慢指针相遇时的情况：

一段时间之后快慢指针相遇在了紫色点的位置，其中慢指针移动的距离就是红色和绿色的部分，即a+b。我们再来看快指针，它移动的范围是红色区域，并且还绕着环走了n圈到了紫色。所以它的移动轨迹是a + n(b+c)。但同时它的移动速度又是慢指针的两倍，所以也等于2a + 2b。

我们联立这两个式子，可以表示出a：

因为a大于0，所以n >= 1。看起来好像还是没啥用， 我们还是没能求出具体值。但实际上已经足够了，我们观察一下等式右边(n-1)(b+c) + c。其中b+c刚好是环的长度，c是黄色的部分。

如果一个指针从头出发，一个指针从相遇的位置出发，它们再次相遇的位置刚好就是环的开始！

我第一次推导出这个结论的时候真的有被震撼到，有种神奇的感觉。但坚持到这里并不容易，很容易中途就放弃了。这也是算法中常见的体验，很多时候看着好像无解，但一旦再坚持坚持，往往又柳暗花明。

推导到了这里再写代码就简单了，只要记录下相遇的位置再出发即可。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        auto fast = head, slow = head;

        while (fast != nullptr) {
            fast = fast->next;
            if (fast == nullptr) return nullptr;
            fast = fast->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        // 注意这里既有可能是有环退出了循环
        // 也有可能是遍历到了结尾
        if (fast == nullptr) return nullptr;

        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

如果你能看到这里，相信你肯定已经明白，为什么它会被微软作为面试题考察候选人了。这样的问题和具体的算法无关，不存在不知道算法就无法解答的情况。这样的问题才能真正考察出一个人的思维能力以及对问题的分析能力，这也是微软这些大公司最看重的地方。

感谢大家的阅读，如果喜欢的话，恳请帮忙转发扩散。算法学习之旅，与你同行。