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