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