女强穿越玄幻完结小说,已完本玄幻小说排行榜,古风

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

環(huán)形鏈表找入口，真的太妙了

本文轉載自微信公眾號「bigsai」，作者bigsai。轉載本文請聯(lián)系bigsai公眾號。

鏈表是否有環(huán)問題看似簡單，但實際處理上有很多需要注意的，這個問題是非常高頻筆試面試題，記憶不牢固容易遺忘，可以認真看看學習一波!當然今天這兩題對應力扣141和力扣142，有個小伙伴就在某手面試中遇到了。

判斷鏈表是否有環(huán)

問題描述：

給定一個鏈表，判斷鏈表中是否有環(huán)。

如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。

如果鏈表中存在環(huán)，則返回 true 。否則，返回 false 。

你能用 O(1)(即，常量)內存解決此問題嗎?

分析：

對于這個問題，如果沒有內存空間的限制，首先想到的就是使用哈希的方法，用一個哈希存儲節(jié)點，然后向下枚舉鏈表節(jié)點：

如果發(fā)現(xiàn)其中有在哈希中，那么就說明有環(huán)返回true。

如果枚舉到最后結束，那就說明沒有環(huán)

但是這樣并不滿足O(1)空間復雜度的要求，我們應該怎么處理呢?

如果鏈表尾部有環(huán)，如果一個節(jié)點枚舉到后面會在閉環(huán)中不斷循環(huán)枚舉，那么怎么樣能高效判斷有環(huán)并且能快速終止呢?

有環(huán)，其實就是第二次、第三次走過這條路才能說它有環(huán)，一個指針在不借助太多空間存儲狀態(tài)下無法有效判斷是否有環(huán)(有可能鏈表很長、有可能已經(jīng)在循環(huán)了)，咱們可以借助快慢指針(雙指針) 啊。

其核心思想就是利用兩個指針：快指針(fast)和慢指針(slow),它們兩個同時從鏈表頭遍歷鏈表，只不過兩者速度不同，如果存在環(huán)那么最終會在循環(huán)鏈表中相遇。

我們在具體實現(xiàn)的時候，可以快指針(fast)每次走兩步，慢指針(slow)每次走一步。如果存在環(huán)的話快指針先進入環(huán)，慢指針后入環(huán)，在慢指針到達末尾前快指針會追上慢指針。

快慢指針如果有相遇那就說明有環(huán)，如果快指針先為null那就說明沒環(huán)。

具體實現(xiàn)代碼為：

 
 
 
 
  
  
  
  /** 
  
  
  
   * Definition for singly-linked list. 
  
  
  
   * class ListNode { 
  
  
  
   *     int val; 
  
  
  
   *     ListNode next; 
  
  
  
   *     ListNode(int x) { 
  
  
  
   *         val = x; 
  
  
  
   *         next = null; 
  
  
  
   *     } 
  
  
  
   * } 
  
  
  
   */ 
  
  
  
  public class Solution { 
  
  
  
      public boolean hasCycle(ListNode head) { 
  
  
  
          ListNode fast=head; 
  
  
  
          ListNode slow=fast; 
  
  
  
          while (fast!=null&&fast.next!=null) { 
  
  
  
              slow=slow.next; 
  
  
  
              fast=fast.next.next; 
  
  
  
              if(fast==slow) 
  
  
  
                  return true; 
  
  
  
          } 
  
  
  
          return false;     
  
  
  
      } 
  
  
  
  }

提高：找到環(huán)的入口

給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。如果鏈表無環(huán)，則返回 null。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置(索引從 0 開始)。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意，pos 僅僅是用于標識環(huán)的情況，并不會作為參數(shù)傳遞到函數(shù)中。

說明：不允許修改給定的鏈表。

你是否可以使用 O(1) 空間解決此題?

這題相比上一題又難了一些，因為如果鏈表成環(huán)，需要找到入口。

分析：

如果不考慮內存使用，我肯定還會首先考慮哈希，將節(jié)點存著然后如果出現(xiàn)第二次則說明有環(huán)并直接返回，實現(xiàn)的代碼也很簡單，走投無路可以用這個方法：

 
 
 
 
  
  
  
  /** 
  
  
  
   * Definition for singly-linked list. 
  
  
  
   * class ListNode { 
  
  
  
   *     int val; 
  
  
  
   *     ListNode next; 
  
  
  
   *     ListNode(int x) { 
  
  
  
   *         val = x; 
  
  
  
   *         next = null; 
  
  
  
   *     } 
  
  
  
   * } 
  
  
  
   */ 
  
  
  
  public class Solution { 
  
  
  
      public ListNode detectCycle(ListNode head) { 
  
  
  
          int pos=-1; 
  
  
  
          Mapmap=new HashMap(); 
  
  
  
          ListNode team=head; 
  
  
  
          while (team!=null) 
  
  
  
          { 
  
  
  
              if(map.containsKey(team)){ 
  
  
  
                  pos=map.get(team); 
  
  
  
                  return team; 
  
  
  
              } 
  
  
  
              else  
  
  
  
                  map.put(team,++pos); 
  
  
  
              team=team.next; 
  
  
  
          } 
  
  
  
          return null; 
  
  
  
      } 
  
  
  
  }

但是怎么使用O(1)的空間復雜度完成這個操作呢?上面一題的思路是使用快慢指針判斷是否有環(huán)，但是怎么鎖定環(huán)的入口呢?

這個題看起來是個算法題，實際上是個數(shù)學推理題。這題的關鍵也是快慢指針，不過需要挖掘更多的細節(jié) 。

回憶一下快慢指針能夠挖掘的細節(jié)：

知道慢指針走了x步，快指針走了2x步，但是僅僅知道這兩個條件還推導不出什么東西，我們能夠進行的操作也只有用O(1)的方法進行一些操作。不過這里面快慢指針和前面有點不同的是我們前面用一個頭結點開始計數(shù)。

我們還可以進行什么操作?

既然知道相遇的這個點在環(huán)內，那么我們可以用一個新的節(jié)點去枚舉一圈看看環(huán)的長度是多少哇!

這里面，我們可以知道fast走的步數(shù)2x，slow走的步數(shù)x，以及環(huán)長y。

我們知道，慢指針是第一次入環(huán)，但快指針可能已經(jīng)走了好幾圈，但是多走的步數(shù)一定是環(huán)的整數(shù)倍(不然不可能在同一個位置相遇)。

那么可以得到快指針步數(shù)=慢指針步數(shù)+n圈環(huán)長度。當然這里n我暫時不知道是多少。換算成公式，那就是 2x=x+ny 消去一個x得到：x=ny。

上面的圖我也標注快指針多走的是整數(shù)圈數(shù)。難點就在這里，需要變通：

快指針多走的x是環(huán)長y的整數(shù)倍n，慢指針走的x也是環(huán)長y的整數(shù)倍n。

那么這樣有什么用呢?

如果某個節(jié)點從起點出發(fā)，走到fast，slow交匯點走的是x步(n*y步)。此時，如果某個指針從fast，slow交匯點開始如果走環(huán)長的整數(shù)倍，那么它到時候還會在原位置。

也就是說從開始head節(jié)點team1走x步，從fast，slow交匯節(jié)點team2走x步，它們最終依然到達fast，slow交匯的節(jié)點，但是在枚舉的途中，一旦team1節(jié)點遍歷的到環(huán)內，那么就和team2節(jié)點重合了，所以它們一旦相等那就是第一個交匯的點了。

具體實現(xiàn)依然要判斷是否有環(huán)，實現(xiàn)代碼為：

 
 
 
 
  
  
  
  /** 
  
  
  
   * Definition for singly-linked list. 
  
  
  
   * class ListNode { 
  
  
  
   *     int val; 
  
  
  
   *     ListNode next; 
  
  
  
   *     ListNode(int x) { 
  
  
  
   *         val = x; 
  
  
  
   *         next = null; 
  
  
  
   *     } 
  
  
  
   * } 
  
  
  
   */ 
  
  
  
  public class Solution { 
  
  
  
      public ListNode detectCycle(ListNode head) { 
  
  
  
          boolean isloop=false; 
  
  
  
          ListNode fast=new ListNode(0);//頭指針 
  
  
  
          ListNode slow=fast; 
  
  
  
          fast.next=head; 
  
  
  
          if(fast.next==null||fast.next.next==null) 
  
  
  
              return null; 
  
  
  
          while (fast!=null&&fast.next!=null) { 
  
  
  
              fast=fast.next.next; 
  
  
  
              slow=slow.next; 
  
  
  
              if(fast==slow) 
  
  
  
              { 
  
  
  
                  isloop=true; 
  
  
  
                  break; 
  
  
  
              } 
  
  
  
          } 
  
  
  
          if(!isloop)//如果沒有環(huán)返回 
  
  
  
              return null; 
  
  
  
          ListNode team=new ListNode(-1);//頭指針 下一個才是head 
  
  
  
          team.next=head; 
  
  
  
          while (team!=fast) { 
  
  
  
              team=team.next; 
  
  
  
              fast=fast.next; 
  
  
  
          } 
  
  
  
          return team; 
  
  
  
      } 
  
  
  
  }

總結

到此，這個問題就介紹到這里，如果有想法歡迎留言，后面會繼續(xù)分享更多數(shù)據(jù)結構與算法介紹以及重要題型，歡迎mark。

本文題目：環(huán)形鏈表找入口，真的太妙了
轉載注明：http://www.fisionsoft.com.cn/article/dpssdho.html

新聞中心

判斷鏈表是否有環(huán)

提高：找到環(huán)的入口

總結

其他資訊