leetcode中怎么判斷鏈表是否有環(huán)

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)leetcode中怎么判斷鏈表是否有環(huán)，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

為啥要刷leetcode？

數(shù)據(jù)結(jié)構(gòu)表征數(shù)據(jù)存儲(chǔ)的格式及操作數(shù)據(jù)的方式，了解這些便于我們大數(shù)據(jù)開發(fā)人員設(shè)計(jì)更好的存儲(chǔ)，讀取，計(jì)算策略。所以在java基礎(chǔ)，大數(shù)據(jù)基礎(chǔ)，大數(shù)據(jù)框架源碼等都有一定基礎(chǔ)之后應(yīng)該去追求寫出更加精致高效的代碼。

最近，在整理java面試題，發(fā)現(xiàn)很多java底層，redis的有序set等存儲(chǔ)結(jié)構(gòu)，spark ，mr等等等我們常用的工具常見的框架都用到了數(shù)據(jù)結(jié)構(gòu)與算法。所以，要想徹底搞明白底層原理，編寫處時(shí)間復(fù)雜度比較低的代碼，還是要去刷一下數(shù)據(jù)結(jié)構(gòu)，況且數(shù)據(jù)結(jié)構(gòu)貌似是bat 數(shù)據(jù)技術(shù)類必須面試的門檻，當(dāng)然你做平臺(tái)開發(fā)最好也會(huì)，不要以為用不到就不去學(xué)，只是你還比較菜。

再回到為啥要刷一下leetcode？

老外都在刷，大學(xué)生也在刷，自己不刷刷，大數(shù)據(jù)搞的再好有毛用，也只是底層開發(fā)。

此處，應(yīng)該吐血。。。

于是乎，今天leetcode破處了，第一個(gè)題是以前沒搞明白的一個(gè)題。題目如下：

Given a linked list, determine if it has a cycle in it.

就是給定一個(gè)鏈表如何判斷其中有環(huán)。leetcode給出的命題及案例如下：

第一次是畢業(yè)的時(shí)候面試被問到這個(gè)題，一臉懵逼，這不刷題誰會(huì)？

最近細(xì)思大致思路有三：

1. 窮舉。從頭遍歷到尾，發(fā)現(xiàn)指向null，說明沒環(huán)。這明顯不靠譜。。。時(shí)間復(fù)雜度O(n)

2. 第三方存儲(chǔ)。邊遍歷邊將指針存入hashset，并且判斷當(dāng)前指針是否存在于hashset，假如存在確定有環(huán)。否則無環(huán)。時(shí)間復(fù)雜度O(n)。

   
   

   public boolean hasCycle(ListNode head) {
       Set<ListNode> nodesSeen = new HashSet<>();
       while (head != null) {
           if (nodesSeen.contains(head)) {
               return true;
           } else {
               nodesSeen.add(head);
           }
           head = head.next;
       }
       return false;
   }

    

3. 快慢指針?？熘羔樏看巫邇刹剑羔樧咭徊?。假如無環(huán)，慢指針永遠(yuǎn)無法追上快指針，時(shí)間復(fù)雜度就是O(n)。假如有環(huán)，那么快指針會(huì)先掉進(jìn)環(huán)里，在那打圈轉(zhuǎn)，快慢指針會(huì)相遇。leetcode 上編寫的java代碼如下：

ListNode walker = head;
        ListNode runner = head;
        while(runner!=null&&runner.next!=null){
            walker = walker.next;
            runner = runner.next.next;
            if(walker == runner){
                return true;
            }
        }
        return false;

上述就是小編為大家分享的leetcode中怎么判斷鏈表是否有環(huán)了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。