leetcode中怎么判斷鏈表是否有環

這期內容當中小編將會給大家帶來有關leetcode中怎么判斷鏈表是否有環，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

為啥要刷leetcode？

數據結構表征數據存儲的格式及操作數據的方式，了解這些便于我們大數據開發人員設計更好的存儲，讀取，計算策略。所以在java基礎，大數據基礎，大數據框架源碼等都有一定基礎之后應該去追求寫出更加精致高效的代碼。

最近，在整理java面試題，發現很多java底層，redis的有序set等存儲結構，spark ，mr等等等我們常用的工具常見的框架都用到了數據結構與算法。所以，要想徹底搞明白底層原理，編寫處時間復雜度比較低的代碼，還是要去刷一下數據結構，況且數據結構貌似是bat 數據技術類必須面試的門檻，當然你做平臺開發最好也會，不要以為用不到就不去學，只是你還比較菜。

再回到為啥要刷一下leetcode？

老外都在刷，大學生也在刷，自己不刷刷，大數據搞的再好有毛用，也只是底層開發。

此處，應該吐血。。。

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

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

就是給定一個鏈表如何判斷其中有環。leetcode給出的命題及案例如下：

第一次是畢業的時候面試被問到這個題，一臉懵逼，這不刷題誰會？

最近細思大致思路有三：

1. 窮舉。從頭遍歷到尾，發現指向null，說明沒環。這明顯不靠譜。。。時間復雜度O(n)

2. 第三方存儲。邊遍歷邊將指針存入hashset，并且判斷當前指針是否存在于hashset，假如存在確定有環。否則無環。時間復雜度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. 快慢指針。快指針每次走兩步，慢指針走一步。假如無環，慢指針永遠無法追上快指針，時間復雜度就是O(n)。假如有環，那么快指針會先掉進環里，在那打圈轉，快慢指針會相遇。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中怎么判斷鏈表是否有環了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。