142. Linked List Cycle II
題目描述
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
<b>Note: Do not modify the linked list.</b>
Follow up:
Can you solve it without using extra space?
解題思路
無視Follow up中的內(nèi)容的話揭厚，很容易就能想到框仔，用一個長度為N的數(shù)組存已經(jīng)經(jīng)過的節(jié)點，然后每次訪問下一個元素時，先在數(shù)組中查找是否訪問過這個元素，若沒有，放入數(shù)組，并繼續(xù)訪問下一個元素；若有荠瘪，則返回這個元素。如果下一個元素為空赛惩，則返回空值哀墓。這樣做我們不難發(fā)現(xiàn)，經(jīng)過第k個元素時喷兼，需要查找k-1個元素篮绰，也就是說，時間復(fù)雜度是的規(guī)模季惯，而且吠各，數(shù)組開辟的額外空間是O(N)的規(guī)模。顯然這不是一個好方法勉抓。
那么我們要如何改善它呢贾漏？數(shù)組的查找顯然是耗費時間非常多的，因此藕筋，如果我們把查找時間降低到O(1)的規(guī)模纵散，那么，整個算法的復(fù)雜度規(guī)模就可以顯著下降了隐圾。查找時間為O(1)的數(shù)據(jù)結(jié)構(gòu)困食，我們馬上就能想到哈希表也就是對應(yīng)c++中的map類型。經(jīng)過這一輪優(yōu)化翎承，我們不難發(fā)現(xiàn)，時間復(fù)雜度已經(jīng)下降到了O(N)的規(guī)模符匾。
然而叨咖，題目要求的不可開辟O(N)復(fù)雜度的額外空間要怎么解決呢？要解決這個問題的核心在于啊胶，我們?nèi)绾未_定鏈表有環(huán)甸各，即什么時候再次經(jīng)過我們訪問過的元素。如果單純的用一個指針來遍歷整個鏈表的話焰坪，我們是很難得知是否訪問過這個元素的趣倾，要確定這個就必須要開辟空間存儲訪問過的元素。但這時某饰，聰明的discussion中的老哥們想到儒恋，如果有兩個不一樣快的指針善绎，同時在遍歷這個鏈表，若它有環(huán)存在诫尽，快的指針就必定能在后面追上慢的指針禀酱；反之，則環(huán)不存在牧嫉。
既然確定環(huán)的問題解決了剂跟，我們又要如何確定環(huán)開始的節(jié)點呢？假設(shè)兩個指針酣藻，快的指針在每次迭代中走兩步曹洽，慢的指針在每次迭代中走一步。當(dāng)快的指針追上慢的指針時辽剧，快的指針比慢的指針走的路程要多一倍送淆。先證明：快的指針會在慢指針到達終點前與它相遇：
k為環(huán)的長度，s為起點到循環(huán)開始的長度抖仅，慢指針走了t次后到達終點坊夫。
慢指針走的路程 = s + k
快指針走的路程 = 2(s + k) = s + k + k + s
顯然，快指針已經(jīng)超過了慢指針撤卢。因此它們一定會在慢指針走到終點前相遇环凿。并且快指針超過了慢指針s的長度。
也就是說放吩，當(dāng)它們相遇時智听，快指針比慢指針多走了kr的長度，假如這時渡紫，快指針的速度變得跟慢指針一樣到推，并且從鏈表頭開始走會怎么樣呢？
由于速度相同惕澎，它們之間的路程差不會再拉開莉测，一直維持在kr。這時候唧喉，讓慢指針和速度跟它一致的快指針一起開始走捣卤，當(dāng)慢指針走到終點并回到循環(huán)開始元素時，快指針由于剛好快它k倍數(shù)的長度八孝，就會在循環(huán)開始元素二者相遇董朝。這時候，我們把它們相遇的元素返回即可干跛。
時間復(fù)雜度分析
慢指針剛好跑完整個鏈表子姜，總時間復(fù)雜度為O(N)。
空間復(fù)雜度分析
兩個指針復(fù)雜度O(1)
源碼
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == NULL || head->next == NULL || head->next->next == NULL)
return NULL;
ListNode* p = head;
ListNode* q = head;
bool cycle = false;
while (p != NULL && q != NULL) {
p = p->next;
if (q->next == NULL)
return NULL;
else {
q = q->next->next;
}
if (p == q) {
cycle = true;
break;
}
}
if (!cycle)
return NULL;
p = head;
while (p != q) {
p = p->next;
q = q->next;
}
return p;
}
};
