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

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

創(chuàng)新互聯(lián)公司成都企業(yè)網站建設服務，提供做網站、成都網站制作網站開發(fā),網站定制,建網站,網站搭建,網站設計,成都響應式網站建設,網頁設計師打造企業(yè)風格網站,提供周到的售前咨詢和貼心的售后服務。歡迎咨詢做網站需要多少錢:18980820575

為啥要刷leetcode？

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

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

再回到為啥要刷一下leetcode？

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

此處，應該吐血。。。

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

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

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

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

最近細思大致思路有三：

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

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

網頁名稱：leetcode中怎么判斷鏈表是否有環(huán)
文章鏈接：http://muchs.cn/article10/pjjhdo.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供網站制作、用戶體驗、服務器托管、小程序開發(fā)、網站內鏈、網站收錄

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)