从链表存在环的问题说起

有这样一个经典的算法题，说是一个单向链表，它内部可能存在环，也可能不存在，用怎样的方法，可以检测出，这个链表是否存在环。下图即是这个形成环的示意，如果单向链表的尾部，指向了链表中的一个节点，而不是指向空，那就构成环了。

接着的一个问题是，怎么检测出这个链表是否有环？

看到这个问题，也许你会觉得，太简单了，但是这个问题只是一个引子。在《求第 K 个数的问题》一文中，我从简入深，逐步展开，把这 “第 K 个数” 的一系列问题翻了个底朝天。我想关于这个链表成环问题，我也利用类似的思路，看看我是不是也能把这一个问题前前后后讲清楚。

判断单向链表是否成环

在进一步思考怎样判断这个成环的问题以前，先考虑一件事情，如果成环，有没有可能成一个以上的环？

从图示上看，似乎说得通，可事实上却是不可能的，因为 M 点需要有两个后继节点，一个用于构成该处的环，一个用于指向 N 的方向，这显然对于一般我们说的单向链表来说，是不可能做到的。

那么，怎么检测单向链表是否成环呢？

网上能见到的最普遍的解决方法就是双指针，一快一慢，从链表头部开始，快的每次走两步，慢的一次走一步，交替进行，直到二者相遇或快指针抵达链表尾部。如果相遇说明存在环。

不过，这是一个巧妙的方法，是一个时间复杂度在 O(n)、空间复杂度在 O(1) 的好方法，却不是唯一的方法。还有一个思路是，用某种方式记录下走过的节点，如果再次遇到了，就说明成环了。这种方法只需要一个指针，且不会重复遍历走过了的节点，但缺点是存在记录走过节点的开销：

• 如果链表节点允许使用某变量标记状态（例如 visited 这样的布尔值），当然可以，且不需要额外的空间复杂度；
• 如果不允许，可以额外使用一个 HashSet 来记录节点，如果存在过，就找到节点了，这种方式的空间复杂度是 O(n)。

再回到那个一快一慢的双指针问题上，有一些基本的问题需要搞清楚。

一快一慢的双指针，在链表成环的情况下，它们一定会遇到吗，有没有可能恰好错过呢？

不会错过，一定会相遇。我们分两种情况考虑：

• 一种情况是快指针恰好落后慢指针一个身位，那么显然慢指针之后的那个位置，就是它们下一个回合碰面的位置；
• 另一种情况是快指针落后更多，那么快指针会慢慢赶上来，因为每一个回合快指针走两步，而慢指针走一步，因此每一个回合二者都可以缩短长度为 1 的距离，直到前面说到的只差一个身位的情况出现。

寻找环入口

那么，下一个自然的问题是，怎样找到那个从单向链表进入环的节点（环入口）？

乍一看这个问题，可能很难找到一个高效的解决方法。我们先退一步，仔细分析一下刚才判断成环的步骤，这里面利用了一个事实，如果链表成环，那么快慢指针一定会相遇。那么一个很自然的问题是，它们会在哪里相遇？

首先，它们肯定在环上相遇，因为直线部分 SN 不可能出现 “追上” 的现象。那么，假设它们相遇的点为 P：

• 对于快指针来说，从起点 S 走到 P 点，假如说绕了 m 圈，环周长为 p，那么一共走了 SN + mp + NP，其中 NP 为最后一圈从 N 逆时针走到 P 的距离。
• 而对于慢指针来说，从 S 走到 P 点，一定只绕了不到一圈，也就是一共走了 SN + NP 的距离。

这里有个问题，为什么慢指针从 S 走到 P 点，一定只绕了不到一圈？

因为对于慢指针来说，在 “运气最背” 的情况下，就是它刚抵达 N 点的时候，快指针恰好已经路过 N 了，因此在 N 没有相遇。那么按照快指针两倍于慢指针速度的情况来说，慢指针一圈之内，也就是快指针两圈之内一定可以发生 “赶上并超过”，那么也就一定会发生 “相遇”（由于前面的结论，它们不会错过）。因此，这种情况下，相遇的时候，慢指针一定还没有绕足一圈。

好，由于我们知道在 P 点相遇的时候，快指针实际走了慢指针两倍的距离，于是得到：

SN + mp +NP = 2 * (SN + NP)

所以，我们得到：

mp = SN + NP

这意味着什么？ 这意味着因为 SN+NP 是环周长的倍数，也就意味着在快慢指针相遇在 P 点的时候，如果这个慢指针继续走 SN 的距离，不管这个 SN 实际会绕多少圈，一定会最终停到 N 点 。

我们虽然还是不知道这个 SN 有多长，但是我们在快慢指针相遇在 P 点的时候，把快指针撤回起点，并且给了快指针一个新指令——你和慢指针一样，每次走一步。这样，慢指针从 P 点开始，逆时针向 N 逼近；快指针从 S 点开始，也以同样的速率向 N 逼近。等它们相遇的时候，恰好就是 N 点，也就是环入口。同时，也获知了 SN 的长度。

计算环周长

如果环入口准确定位了，那么环周长也自然不成问题了。

从环入口开始计数，直到若干步后，重新回到环入口。知道了环周长，根据前面获知的 SN，也就知道了 NP（从环入口 N 逆时针遍历到快慢指针相遇点 P）的距离。

判断链表相交

链表相交，指的是两个不同的链表，链表头不同，但是链表尾部却相同。如图所示：

其中，一个链表从头部 S 开始，另一个从头部 T 开始，二者相交在节点 N，最后共同收尾于 E。

怎样判断链表是否相交，如果是，又怎样找到相交的节点 N？

根据前面寻找环入口问题的启示，如果 SN 的长度等于 TN，那么一个指针从 S 开始，另一个从 T 开始，一样的速率前进，相交的地方就是 N。

但是 SN 和 TN 并不一定相等。

不过也没关系，先对于链表 S-N-E，遍历一遍，得到长度 l1；再对于链表 T-N-E，遍历一遍，得到长度 l2，对于二者中长度较长的一个，让这个指针单独先走一段（以下图为例，从 S 走到 Q），走的这段长度恰好为 l1 和 l2 的差值，把这段差值给抹平。这样一来，QN 就等于 TN 了，这样两个指针就可以同样速率往后前进了，相遇的 N 点就是相交的节点；如果一直不相遇，那就是没有相交。

链表相交和链表成环一起出现

都很简单是不是？有了前面的铺垫，下面来讨论最复杂的问题。

假如说，链表成环和链表相交一起出现，即分别有两个链表，它们可能成环，也可能相交，还可能既成环、又相交。现在，怎样判断它们是否成环，如果成环，环入口在哪里？是否相交，如果相交，相交点又在哪里？

看起来似乎问题一下子复杂了很多，可是仔细观察一下这两个问题，它们的地位不是均等的——

• 成环的判断，并不依赖于相交的判断。换言之，无论两个链表是否相交，都可以利用前面所述的成环判断，和环入口的计算方式求得。
• 可是相交的判断却依赖于成环的判断。换言之，要求相交的点需要知道链表的长度，而一旦链表成环了，这个长度就不再能用通用的方法来求解了。

因此，先判断链表是否成环，并且分别求出这两个链表的环入口（如果成环的话），之后再考虑链表相交的问题。

接着，关于成环和相交，有如下的结论：

• 如果这两个链表，一个成环，而另一个不成环，那么它们二者肯定不相交。 这个结论是显然的，因为相交，意味着这个环是共用的，那么自然不可能一个成环，而另一个不成环了。
• 如果这两个链表都不成环，那么问题退化为前面讲的相交问题。
• 如果这两个链表都成环，那么问题就比较有意思了，下面我们按照相交点出现的位置来分别讨论。

这种情况下，我们把环入口的点视作两个链表的尾部，然后可以用前面所述的算法求得相交的点。

如果在遍历到环入口以前，找到了两个链表相交的节点，那么我们遇到了 情况一，相交的节点先于成环的节点出现 ：

反之，如果遍历到环入口时，依然没有发现相交的节点，那么存在下面所述的情况二和情况三：

情况二，成环且不相交，相当于两个独立的带环链表 ：

情况三，环入口和相交的节点一起出现 ：

有没有可能有情况四，即先出现环入口，再出现相交的节点？

不可能。因为前面已经介绍了，相交就意味着一旦有环，这个环就是两个链表共用的，因此这个环入口一旦出现，就意味着一个链表连上了另一个链表的环，也就意味着相交点也出现了。因此，这种情况下二者是一起出现的，不可能出现环入口早于相交节点的情况。

那么现在的问题是，怎样区分情况二和情况三？

既然两个环入口都找到了，那么以任意一个环入口作为起点，开始遍历，绕环一周，如果期间遇到了另一个环入口，说明是情况三，否则则是情况二。

好，这个问题就讨论到这里。你也可以看到，如果单独拿出最后一个问题来，这是一个有着相当复杂度的问题。不过如果逐步深入进来的话，应该就好很多。

记得在差不多快要十年前了，我 “莫名其妙” 地参加了微软的面试，而电话面试问的题目就是本文一开始的链表成环判断的问题。由于对外企面试的玩法一无所知，我被虐得体无完肤。现在看起来这实在是一个太过普通的问题，但当时的我对于算法的认识是非常浅的，也没有给出一个非常好的解决办法。但是从那一天开始，我才真正算是逐步开始接触并学习算法，因此这篇文章，也算对它小小的纪念。

最后，我想说明的是，在分析上面这些问题的时候，我没有写一点代码。我觉得，这样的纯算法问题，只要思路清楚了，代码基本不是什么问题。