摘要：初始化時指針走兩步，指針走一步，不停遍歷的變化最后快慢指針又相遇了，循環(huán)結(jié)束，代碼實現(xiàn)如下復雜度分析，假設(shè)鏈表長度為時間復雜度，鏈表無環(huán)時，快指針會先到達尾部，時間就是如果有環(huán)，那么假設(shè)環(huán)部長度為，時間就是，也就是空間復雜度
上一篇文章我們分析了下鏈表之反轉(zhuǎn)單向鏈表，這篇文章我們來分析下另外一個關(guān)于鏈表的經(jīng)典題目。
判斷鏈表是否有環(huán)(在leetcode上的題目地址：環(huán)形鏈表)
題目描述
給定一個鏈表，判斷鏈表中是否有環(huán)
解決方案
一、可以使用hash表來實現(xiàn)，遍歷鏈表，每個節(jié)點放入hash表中，如果hash表中包含了某個節(jié)點，那么說明有重復節(jié)點存在，即是有環(huán)。如果沒環(huán)，那么鏈表會遍歷結(jié)束。代碼如下：
public static > boolean hasCycle1(Node head) {
HashSet> set = new HashSet<>();
for(Node n=head;n!=null;n=n.getNext()) {
if(set.contains(n)) {
return true;
}
set.add(n);
}
return false;
}
備注Node類參照上篇文章
復雜度分析，假設(shè)鏈表長度為n
時間復雜度：每個元素都要遍歷一遍，所以時間為O(n)，每次訪問hash表時間為O(1)。
空間復雜度：O(n)，n個元素都會添加到hash表中。
二、上面這種方法可以解決，但是需要借助額外的空間復雜度，能否不使用額外空間解決此題呢？答案是有的，使用快慢指針，想象下，兩個人在一個環(huán)形跑道上賽跑，跑得快的一定會追上跑的慢的那個人吧。下面用圖示來展示下整個過程。
初始化時：
fast指針走兩步，slow指針走一步，不停遍歷的變化：
最后快慢指針又相遇了，循環(huán)結(jié)束，代碼實現(xiàn)如下：
public static > boolean hasCycle(Node head) {
if(head == null || head.getNext() == null) {
return false;
}
Node slow = head;
Node fast = head;
while(fast != null && fast.getNext() != null) {
slow = slow.getNext();
fast = fast.getNext().getNext();
if(slow == fast) {
return true;
}
}
return false;
}
復雜度分析，假設(shè)鏈表長度為n
時間復雜度：O(n)，鏈表無環(huán)時，快指針會先到達尾部，時間就是O(n)；如果有環(huán)，那么假設(shè)環(huán)部長度為K，時間就是O(n+k)，也就是O(n)
空間復雜度：O(1)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71735.html
