问题描述
我们给出一个单向链表，我们需要看看这个链表是否有循环的部分，如果有循环，返回起始的节点，如果没有循环存在，我们返回null。比如下图中给出的链表我们需要返回值为5的节点，因为这是循环的开始。
那让我们来看一下如何才能实现？首先，我们定义输入为链表的头节点，输出是循环部分的起始节点，极端情况下输入的链表头节点为空，即null，那么也直接返回null。我们有多种方式来实现这个方法。
解法一
一个非常简单的方法就是我们从链表的头节点开始读取这个链表的每个节点，并且用hash表存储下所有我们访问的节点，当我们再次访问hash表中已经存在的节点的时候，我们就知道这个循环是存在的，如果查询到链表的末端，即某个节点的指向的next节点为null时候，说明这个链表并不存在循环的部分。
这个算法的时间复杂度是O(n)，因为最坏情况就是遍历整个链表；空间复杂度是O(n)，因为我们需要将每个经过的节点的信息存到hash表里。
解法二
这个方法中我们不使用额外的空间去存储所有数据，我们可以用两个循环来实现，外循环一个接一个地遍历链表的节点，内循环从链表的头节点开始往后遍历，一直到外循环节点的后一个节点，如果内循环执行过程中两次遇到外循环所处的节点的下一个节点，则说明存在循环，且刚刚提到的“下一个节点”就是循环的起始节点，如果外循环到达链表末尾，则说明没有循环部分的存在。
比如下图中红色箭头为外循环，当前它到达值为7的节点B，他的下一节点是节点A，且我们记录节点A的在内循环中的重复情况，黄色箭头为内循环，它从链表头节点开始向后遍历，第一次正常经过A节点时候记录一次，第二次到达外循环节点B的下一节点A时候再记录一次，判断发现A节点被内循环了2次，所以节点值为5的节点为链表的循环部分的起始节点。
这个解法由于使用到了内外循环，所以时间复杂度是O(n²)，由于只是需要变量来计算重复到达的次数，所以空间复杂度是O(1)。
解法三
前一个算法时间复杂度居然是O(n²)，显然不是一个好的方法，那有没有线性时间复杂度的呢？答案是有的。
我们可以借助两个指针来实现，一个叫快指针（fast pointer），一个叫慢指针（slow pointer）。如上图中，快指针（红色指针）往后走两个节点，慢指针（黄色指针）往后走一个节点，如果这个链表没有循环部分，那么两个节点永远不可能指向同一个节点，也就是说，当两个指针指向同一个节点的时候，就说明这个链表存在循环部分。
图中我们可以看到红色和黄色两个指针会在值为9的节点相遇。然后我们很容易找到循环部分长度，我们只需要继续移动红色指针并逐步记住步骤,直到指向黄色指针，就可以得到这里的循环长度，本例中长度是4。
最后我们使用另外两个指针（绿色和蓝色指针），蓝色指针（对应代码中second指针）从头节点开始，绿色指针（对应代码中first指针）往后走4个节点（同循环长度），接着这两个指针一个接一个往后走，直到他们指向同一个节点，这个节点就是循环起始节点。本例中是值为5对应的节点。
这个解法时间从上面的解说和程序来看复杂度是O(n)，由于只用了4个指针变量，所以空间复杂度是O(1)。
解法四
当然，我们也可以不计算循环部分长度，可以在快慢指针相遇的时候通过一些计算来解决这个问题，我们假设X是从头节点到循环部分起始节点的长度，Y是循环部分起始节到快慢指针相遇的节点的长度。因为慢指针走过节点数为X+Y，快指针由于速度是慢指针的两倍，所以走过节点数是2(X+Y)，而他们的路程差刚好是循环部分的长度，所以循环长度C=X+Y。
当快慢指针相遇后，将慢指针置为链表头节点，让他与快指针都以每次一个节点的顺序向后移动，当他们再次相遇的时候，它们所在的节点就是循环部分开始的节点。代码实现如下：
这种算法时间复杂度是O(n)，由于只用了2个指针变量，所以空间复杂度是O(1)。
继续阅读
阅读原文