环形链表¶
统计信息：字数 4023 阅读9分钟
No.1 如何检测链表形成环？¶
给定一个链表，判断链表中是否形成环。
思路¶
思路一: 循环一遍，用 Set 数据结构保存节点，利用节点的内存地址来进行判重，如果同样的节点走过两次，则表明已经形成了环。
思路二: 利用快慢指针，快指针一次走两步，慢指针一次走一步，如果两者相遇，则表明已经形成了环。
可能你会纳闷，为什么思路二用两个指针在环中一定会相遇呢？
其实很简单，如果有环，两者一定同时走到环中，那么在环中，选慢指针为参考系，快指针每次相对参考系向前走一步，终究会绕回原点，也就是回到慢指针的位置，从而让两者相遇。如果没有环，则两者的相对距离越来越远，永远不会相遇。
接下来我们来编程实现。
方法一: Set 判重¶
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = (head) => {
let set = new Set();
let p = head;
while(p) {
// 同一个节点再次碰到，表示有环
if(set.has(p)) return true;
set.add(p);
p = p.next;
}
return false;
}
方法二: 快慢指针¶
var hasCycle = function(head) {
let dummyHead = new ListNode();
dummyHead.next = head;
let fast = slow = dummyHead;
// 零个结点或者一个结点，肯定无环
if(fast.next == null || fast.next.next == null)
return false;
while(fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
// 两者相遇了
if(fast == slow) {
return true;
}
}
return false;
};
No.2 如何找到环的起点¶
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
说明：不允许修改给定的链表。
思路分析¶
刚刚已经判断了如何判断出现环，那如何找到环的节点呢？我们来分析一波。
看上去比较繁琐，我们把它做进一步的抽象:
设快慢指针走了x秒，慢指针一秒走一次。
对快指针，有: 2x - L = m * S + Y -----①
对慢指针，有: x - L = n * S + Y -----②
其中，m、n 均为自然数。
① * 2 - ② 得:
L = (m - n) * S - Y-----③
好，这是一个非常重要的等式。我们现在假设有一个新的指针在 L 段的最左端，慢指针现在还在相遇处。
让新指针和慢指针都每次走一步，那么，当新指针走了 L 步之后到达环起点，而与此同时，我们看看慢指针情况如何。
由③式，慢指针走了(m - n) * S - Y个单位，以环起点为参照物，相遇时的位置为 Y，而现在由Y + (m - n) * S - Y即(m - n) * S，得知慢指针实际上参照环起点，走了整整(m - n)圈。也就是说，慢指针此时也到达了环起点。
结论
现在的解法就很清晰了，当快慢指针相遇之后，让新指针从头出发，和慢指针同时前进，且每次前进一步，两者相遇的地方，就是环起点。
编程实现¶
懂得原理之后，实现起来就容易很多了。
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
let dummyHead = new ListNode();
dummyHead.next = head;
let fast = slow = dummyHead;
// 零个结点或者一个结点，肯定无环
if(fast.next == null || fast.next.next == null)
return null;
while(fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
// 两者相遇了
if(fast == slow) {
let p = dummyHead;
while(p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
};