今天在Leetcode大杀特杀的时候，偶然看到一道题，使用了双指针的巧妙解法，在这里分享给大家！
题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
常规解法
题目相关的标签，有哈希表和双指针，首先最常见就是使用HashSet。
沿着链表开始，逐步判断是否有重复的node，如果为true，那么这个节点就是循环开始的节点了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode detectCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<>();
ListNode node = head;
while(node != null){
if(set.contains(node)){
return node;
}else {
set.add(node);
node = node.next;
}
}
return null;
}
但是一看结果才打败了20%的速度，显然还有更巧妙的方法，那么就是双指针了
双指针解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ListNode detectCycle1(ListNode head) {
if (head == null) return null;
ListNode slower = head, faster = head;
// fast两倍于slow，fast多于slow一圈循环，所以slow的位置就是一圈循环的长度
while (faster != null && faster.next != null) {
slower = slower.next;
faster = faster.next.next;
if (slower == faster) break;
}
if (faster == null || faster.next == null) return null;
slower = head;
// fast位于循环内，fast走完剩下的循环，slow走到循环开始的地方会相交，记录节点
// 如果继续行进，slow从交点到现在的fast位置，fast也交点走到现在的位置
// slow走的路程是从开始到这个点等于一个循环的长度
// fast走完剩下的，再走交点后开始的也是一个循环的长度
while (slower != faster) {
slower = slower.next;
faster = faster.next;
}
return slower;
}
条件一：fast是slow速度的两倍，找到一个定点B
条件二：fast相对于slow多跑了一个循环
那么使用小学加减法就可以知道 2x - x = 1 cycle，slow的路程也是一个cycle的长度，即OAB = 1 cycle
因此第二段程序，我们将中间重叠的部分擦去
那么OA = B→A
所以再以同样的速度前进就可以在开始的节点相交：A
大功告成！！完美
关注我，分享更多有趣的算法知识！！
