小灰算法(一): 快慢指针求解链表是否有环
文章参考自书籍：《漫画算法-小灰的算法之旅》-魏梦舒
单向有环链表
如图是一个有环的单向链表，那么我们如何判断一个单向链表有环吗？会被大家常想到的方法是穷举遍历或者借助一个hashSet来判断。穷举的时间复杂度是O(N*N)，借助hashSet的时间复杂度是O(N)，空间复杂度是O(N)。
所以我们今天来介绍一种稍微更优的算法来求解单向链表是否有环。首先我们使用两个指针p1和p2指向链表头结点。然后让p1以速度1向后移动，p2以速度2向后移动。如果两个指针会相遇，则表示此链表有环。
-
首先p1和p2指向头结点：
-
p1一次移动一步到2这个节点，p2一次移动两步到5这个节点
-
继续移动
-
继续...
-
在3这个节点相遇，则表示此链表有环
为什么这样就能判断链表有环了呢？我们不妨试想一下，如果两个速度不同的人在操场绕圈一直跑，一段时间后速度快的人自然又追上慢的那位了。原因就是因为操场也是个环。这种算法的时间复杂度是O(N)，空间复杂度是O(1)。
- 接下来我们用代码实现一下
/**
* 链表节点
* @author chenchen
*/
public class Node {
private int value;
private Node next;
public Node (int value) {
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
/**
* 判断一个单向链表是否有环
* @author chenchen
*/
public class Test {
public static void main(String[] args) {
// 1. 创建一个有环单向链表
Node n1 = new Node(8);
Node n2 = new Node(2);
Node n3 = new Node(5);
Node n4 = new Node(6);
Node n5 = new Node(3);
Node n6 = new Node(9);
Node n7 = new Node(7);
n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(n7);
n7.setNext(n4);
// 2. 判断是否有环
boolean result = isLoopLink(n1);
System.out.println(result);
}
/**
* 判断此单向链表是否有环
* @param head Node
* @return boolean
*/
private static boolean isLoopLink(Node head) {
// 1. p1,p2指向头结点
Node p1 = head;
Node p2 = head;
// 2. p1和p2以不同的速度向后移动
while (null != p1 && null != p2.getNext()) {
p1 = p1.getNext();
p2 = p2.getNext().getNext();
if (p1 == p2) {
return true;
}
}
return false;
}
}
很明显，咱这个环的长度是4，入环的节点是6. 所以有了下面两个扩展问题大家来思考一下。
-
扩展一：如何求出环的长度
思路：首次相遇后，p2和p1继续移动，下次相遇时p2比p1整整多跑了一圈。所以环长=速度差*前进次数 -
扩展二：如何求出入环节点
如图，我们假设头结点到入环点的距离是D, 入环点到首次相遇点的距离是s1, 首次相遇点继续往后走再回到入环点的距离是s2. 那么两指针首次相遇时各走了多少距离呢。
p1：D+S1
p2: D+S1+S2+S1
因为p2速度是p1的二倍，所以有
2(D+S1) = D+S1+S2+S1
整理得到: D = S2
有了这个结论那么我们将p1重置回头结点，p2在首次相遇点。两个指针都是每次移动一步，这样再次相遇时就是入环点了。
作者 [@没有故事的老大爷][1]
[1]: https://www.chenchen.zone/
