文章參考自書(shū)籍：《漫畫(huà)算法-小灰的算法之旅》-魏夢(mèng)舒
如圖是一個(gè)有環(huán)的單向鏈表，那么我們?nèi)绾闻袛嘁粋€(gè)單向鏈表有環(huán)嗎？會(huì)被大家常想到的方法是窮舉遍歷或者借助一個(gè)hashSet來(lái)判斷。窮舉的時(shí)間復(fù)雜度是O(N*N)遥昧，借助hashSet的時(shí)間復(fù)雜度是O(N)，空間復(fù)雜度是O(N)。
所以我們今天來(lái)介紹一種稍微更優(yōu)的算法來(lái)求解單向鏈表是否有環(huán)鸥诽。首先我們使用兩個(gè)指針p1和p2指向鏈表頭結(jié)點(diǎn)。然后讓p1以速度1向后移動(dòng)箕憾，p2以速度2向后移動(dòng)衙传。如果兩個(gè)指針會(huì)相遇，則表示此鏈表有環(huán)厕九。
-
首先p1和p2指向頭結(jié)點(diǎn)：
p1一次移動(dòng)一步到2這個(gè)節(jié)點(diǎn)蓖捶，p2一次移動(dòng)兩步到5這個(gè)節(jié)點(diǎn)
-
繼續(xù)移動(dòng)
-
繼續(xù)...
-
在3這個(gè)節(jié)點(diǎn)相遇，則表示此鏈表有環(huán)
為什么這樣就能判斷鏈表有環(huán)了呢扁远？我們不妨試想一下俊鱼，如果兩個(gè)速度不同的人在操場(chǎng)繞圈一直跑刻像，一段時(shí)間后速度快的人自然又追上慢的那位了。原因就是因?yàn)椴賵?chǎng)也是個(gè)環(huán)并闲。這種算法的時(shí)間復(fù)雜度是O(N)细睡，空間復(fù)雜度是O(1)怨咪。
- 接下來(lái)我們用代碼實(shí)現(xiàn)一下
/**
* 鏈表節(jié)點(diǎn)
* @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;
}
}
/**
* 判斷一個(gè)單向鏈表是否有環(huán)
* @author chenchen
*/
public class Test {
public static void main(String[] args) {
// 1. 創(chuàng)建一個(gè)有環(huán)單向鏈表
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. 判斷是否有環(huán)
boolean result = isLoopLink(n1);
System.out.println(result);
}
/**
* 判斷此單向鏈表是否有環(huán)
* @param head Node
* @return boolean
*/
private static boolean isLoopLink(Node head) {
// 1. p1,p2指向頭結(jié)點(diǎn)
Node p1 = head;
Node p2 = head;
// 2. p1和p2以不同的速度向后移動(dòng)
while (null != p1 && null != p2.getNext()) {
p1 = p1.getNext();
p2 = p2.getNext().getNext();
if (p1 == p2) {
return true;
}
}
return false;
}
}
很明顯彼硫，咱這個(gè)環(huán)的長(zhǎng)度是4，入環(huán)的節(jié)點(diǎn)是6. 所以有了下面兩個(gè)擴(kuò)展問(wèn)題大家來(lái)思考一下糠排。
擴(kuò)展一：如何求出環(huán)的長(zhǎng)度
思路：首次相遇后犀填，p2和p1繼續(xù)移動(dòng)蠢壹，下次相遇時(shí)p2比p1整整多跑了一圈。所以環(huán)長(zhǎng)=速度差*前進(jìn)次數(shù)-
擴(kuò)展二：如何求出入環(huán)節(jié)點(diǎn)
如圖九巡，我們假設(shè)頭結(jié)點(diǎn)到入環(huán)點(diǎn)的距離是D, 入環(huán)點(diǎn)到首次相遇點(diǎn)的距離是s1, 首次相遇點(diǎn)繼續(xù)往后走再回到入環(huán)點(diǎn)的距離是s2. 那么兩指針首次相遇時(shí)各走了多少距離呢图贸。
p1：D+S1
p2: D+S1+S2+S1
因?yàn)閜2速度是p1的二倍，所以有
2(D+S1) = D+S1+S2+S1
整理得到: D = S2
有了這個(gè)結(jié)論那么我們將p1重置回頭結(jié)點(diǎn)冕广，p2在首次相遇點(diǎn)疏日。兩個(gè)指針都是每次移動(dòng)一步，這樣再次相遇時(shí)就是入環(huán)點(diǎn)了撒汉。
作者 [@沒(méi)有故事的老大爺][1]
[1]: https://www.chenchen.zone/
