Linked List Cycle II 環(huán)形鏈表 II
問題描述：
給定一個鏈表的頭節(jié)點(diǎn) head ，返回鏈表開始入環(huán)的第一個節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。
如果鏈表中有某個節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識鏈表的實際情況。
不允許修改 鏈表。
鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [ 0 , 1 0 4 ] ? 1 0 5 < = N o d e . v a l < = 1 0 5 p o s 為 ? 1 或者鏈表中的一個有效索引 鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [0, 10^4]\\ -10^5 <= Node.val <= 10^5\\ pos 為 -1 或者鏈表中的一個 有效索引 鏈表中節(jié)點(diǎn)的數(shù)目范圍是[0,104]?105<=Node.val<=105pos為?1或者鏈表中的一個有效索引
分析
和昨天的環(huán)形鏈表類似，利用哈希可以在 O ( N ) O(N) O(N)的時間下，找到第一個節(jié)點(diǎn)。
另一種就是空間為常數(shù)的快慢指針，就是昨天發(fā)的那個，它還有個比較學(xué)術(shù)的名字，Floyd判圈算法(Floyd Cycle Detection Algorithm)，它的應(yīng)用場景很廣泛，可以自行Bing，Google。
它的思路比較簡單，如果存在環(huán)，那么先找到快慢指針在環(huán)中的相遇的點(diǎn) x，然后再讓2個指針分別從head，x出發(fā)，直到2者相遇，就是環(huán)的入口點(diǎn)。
思路很簡單，但是大部分人還是不一定能AC。
為什么按照這個思路，可以找到的點(diǎn)一定是入口點(diǎn)?
討論的前提是有環(huán)。
假設(shè)入口點(diǎn)是y，那么從
h
e
a
d
head
head到達(dá)y需要 a步，從y到達(dá)2指針的相遇點(diǎn)x要走b步,b一定是小于n的,從x繼續(xù)走c步到達(dá)入口y,所以環(huán)的大小為
b
+
c
b+c
b+c。
f
a
s
t
走的路程
=
a
+
(
k
+
1
)
(
b
+
c
)
+
b
fast 走的路程 = a+ (k+1)(b+c) + b
fast走的路程=a+(k+1)(b+c)+b。 a 是無環(huán)段，b是環(huán)的入口到x的路程，而
(
k
+
1
)
(
b
+
c
)
(k+1)(b+c)
(k+1)(b+c) 就是跑環(huán)的圈數(shù)，
k
>
=
0
k>=0
k>=0。
而
s
l
o
w
的路程
=
a
+
b
slow的路程 = a+b
slow的路程=a+b ,因為fast的速度是slow的2倍，所以路程也是其2倍，即
a
+
b
+
(
k
+
1
)
(
b
+
c
)
=
2
?
(
a
+
b
)
(
k
+
1
)
(
b
+
c
)
=
a
+
b
k
(
b
+
c
)
+
c
=
a
a+b +(k+1)(b+c) = 2*(a+b)\\ (k+1)(b+c) = a+b\\ k(b+c)+c = a
a+b+(k+1)(b+c)=2?(a+b)(k+1)(b+c)=a+bk(b+c)+c=a
到這里就會可以得到一個結(jié)論，設(shè)置2個指針分別從點(diǎn)x和head出發(fā)，每次一步，如果相遇就是入口點(diǎn)。
如果你無法理解這個結(jié)論.
提示你可以從路程的角度來思考，即一個從x出發(fā)的指針，它可能走c，或者是k(b+c)+c,然后恰好與另一個指針在入口相遇。
時間復(fù)雜度 O ( N ) 時間復(fù)雜度O(N) 時間復(fù)雜度O(N)
空間復(fù)雜度 O ( 1 ) 空間復(fù)雜度O(1) 空間復(fù)雜度O(1)
代碼
哈希
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet();
ListNode p = head;
while(p!=null){
if(!set.add(p)) return p;
p = p.next;
}
return null;
}
時間復(fù)雜度 O ( N ) O(N) O(N)
空間復(fù)雜度 O ( N ) O(N) O(N)
快慢指針
public ListNode detectCycle(ListNode head) {
if(head==null||head.next==null) return null;
ListNode vh = new ListNode(-1);
vh.next = head;
ListNode f = vh, s = vh;
while(f!=null&&f.next!=null){
f = f.next.next;
s = s.next;
if(f==s) break;
}
if(f==null||f.next==null) return null;
ListNode p = vh, q = f;
while(p!=q){
p = p.next;
q = q.next;
}
return q;
}
時間復(fù)雜度 O ( N ) O(N) O(N)
空間復(fù)雜度 O ( 1 ) O(1) O(1)
Tag
LinkedList
Hash文章來源：http://www.zghlxwxcb.cn/news/detail-619546.html
Two Pointers文章來源地址http://www.zghlxwxcb.cn/news/detail-619546.html
到了這里，關(guān)于【LeetCode 算法】Linked List Cycle II 環(huán)形鏈表 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
