如何判断一个链表是否有环，如果有，则返回第一个进入环的节点，没有则返回null

p style="text-indent: 2em; text-align: left;">这道题需要分析的情况非常多，同时因为有额外空间复杂度为O (1)的限制，所以实现起来也比较困难。

本题可以拆分成三个子问题，每个问题都可以作为一道独立的算法题，具体如下。

问题一：如何判断一个链表是否有环，如果有，则返回第一个进入环的节点，没有则返回null。

问题二：如何判断两个无环链表是否相交，相交则返回第一个相交节点，不相交则返回null。

问题三：如何判断两个有环链表是否相交，相交则返回第一个相交节点，不相交则返回null。

注意：如果一个链表有环，另外一个链表无环，它们是不可能相交的，直接返回null。

下面逐一分析每个问题。

问题一：如何判断一个链表是否有环，如果有，则返回第一个进入环的节点，没有则返回null。

如果一个链表没有环，那么遍历链表一定可以遇到链表的终点；如果链表有环，那么遍历链表就永远在环里转下去了。如何找到第一个入环节点，具体过程如下：

1．设置一个慢指针slow和一个快指针fast。在开始时，slow和fast都指向链表的头节点head。然后slow每次移动一步，fast每次移动两步，在链表中遍历起来。

2．如果链表无环，那么fast指针在移动的过程中一定先遇到终点，一旦fast到达终点，说明链表是没有环的，直接返回null，表示该链表无环，当然也没有第一个入环的节点。

3．如果链表有环，那么fast指针和slow指针一定会在环中的某个位置相遇，当fast和slow相遇时，fast指针重新回到head的位置，slow指针不动。接下来，fast指针从每次移动两步改为每次移动一步，slow指针依然每次移动一步，然后继续遍历。

4.fast指针和slow指针一定会再次相遇，并且在第一个入环的节点处相遇。证明略。

注意：你也可以用哈希表完成问题一的判断，但是不符合题目关于空间复杂度的要求。

问题一的具体实现请参看如下代码中的getLoopNode方法。

public Node getLoopNode(Node head) { if (head == null || head.next == null || head.next.next == null) { return null; } Node n1 = head.next; // n1 -> slow Node n2 = head.next.next; // n2 -> fast while (n1 ! = n2) { if (n2.next == null || n2.next.next == null) { return null; } n2 = n2.next.next; n1 = n1.next; } n2 = head; // n2 -> walk again from head while (n1 ! = n2) { n1 = n1.next; n2 = n2.next; } return n1; }

如果解决了问题一，我们就知道了两个链表有环或者无环的情况。如果一个链表有环，另一个链表无环，那么这两个链表是无论如何也不可能相交的。能相交的情况就分为两种，一种是两个链表都无环，即问题二；另一种是两个链表都有环，即问题三。

问题二：如何判断两个无环链表是否相交，相交则返回第一个相交节点，不相交则返回null。

如果两个无环链表相交，那么从相交节点开始，一直到两个链表终止的这一段，是两个链表共享的。解决问题二的具体过程如下：

1．链表1从头节点开始，走到最后一个节点（不是结束），统计链表1的长度记为len1，同时记录链表1的最后一个节点记为end1。

2．链表2从头节点开始，走到最后一个节点（不是结束），统计链表2的长度记为len2，同时记录链表2的最后一个节点记为end2。

3．如果end1! =end2，说明两个链表不相交，返回null即可；如果end==end2，说明两个链表相交，进入步骤4来找寻第一个相交节点。

4．如果链表1比较长，链表1就先走len1-len2步；如果链表2比较长，链表2就先走len2-len1步。然后两个链表一起走，一起走的过程中，两个链表第一次走到一起的那个节点，就是第一个相交的节点。

例如：链表1长度为100，链表2长度为30，如果已经由步骤3确定了链表1和链表2一定相交，那么接下来，链表1先走70步，然后链表1和链表2一起走，它们一定会共同进入第一个相交的节点。

问题二的具体实现请参看如下代码中的noLoop方法。

public Node noLoop(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; } Node cur1 = head1; Node cur2 = head2; int n = 0; while (cur1.next ! = null) { n++; cur1 = cur1.next; } while (cur2.next ! = null) { n--; cur2 = cur2.next; } if (cur1 ! = cur2) { return null; } cur1 = n > 0 ? head1 : head2; cur2 = cur1 == head1 ? head2 : head1; n = Math.abs(n); while (n ! = 0) { n--; cur1 = cur1.next; } while (cur1 ! = cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; }

问题三：如何判断两个有环链表是否相交，相交则返回第一个相交节点，不相交则返回null。

考虑问题三的时候，我们已经得到了两个链表各自的第一个入环节点，假设链表1的第一个入环节点记为loop1，链表2的第一个入环节点记为loop2。以下是解决问题三的过程：

1．如果loop1==loop2，那么两个链表的拓扑结构如图2-4所示。

图2-4

这种情况下，我们只要考虑链表1从头开始到loop1这一段与链表2从头开始到loop2这一段，在那里第一次相交即可，而不用考虑进环该怎么处理，这就与问题二类似，只不过问题二是把null作为一个链表的终点，而这里是把loop1(loop2)作为链表的终点。但是判断的主要过程是相同的。

2．如果loop1! =loop2，两个链表不相交的拓扑结构如图2-5所示。两个链表相交的拓扑结构如图2-6所示。