圓形鏈表邏輯

/** 
* 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) { 
     if(head == null){ 
      return false; 
     } 
      ListNode slow = head; 
      ListNode fast = head.next; 

      while((slow != null) && (fast != null) && (slow.next != null) && (fast.next != null)){ 
      if(slow == fast){ 
       return true; 
      } 
      slow = slow.next; 
      fast = fast.next.next; 

      } 

      return false; 
    } 
}

對於檢測循環鏈表，我們使用2指針技術，速度慢，速度快。圓形鏈表邏輯

我的問題是，如果列表是圓形列表，我怎麼知道指針必須是在某個點相交？

來源

2017-04-14 user7487099

順便說一句，在循環鏈表中不需要兩個指針，它主要用於實現隊列和斐波那契堆。當你到達第一個節點時，你停止遍歷。 –

@PorkkoM這個問題不是關於*使用*循環鏈，而是關於檢測非循環列表的損壞鏈的鏈表實現。 – Andreas

關於複雜性，爲什麼不同時有一個鏈表和一個集合？關注鏈接列表中項目的順序並跟蹤索引結構中的重複（循環）。那麼爲什麼不使用已經存在的[LinkedHashSet ]（https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashSet.html）。如果你想添加任何自定義行爲（如拋出異常，而不是在add（）上返回false），那麼已經實現並測試過了，你可以繼承它嗎？ – andreim

看看手錶。這是一個數字1到12然後圈回到1的圓形列表。

大手快速移動，小手移動緩慢，都在同一方向移動，並在同一點開始（頂部= 12）。

由於列表（邊緣）是圓形的，大手最終會回到小手。如何快速取決於速度差異，但會趕上。如果趕上了，名單必須是循環的。

如果它沒有趕上，但得到列表的結尾，列表不是循環的。

即使列表沒有回到起點，例如，如果12圈回到9，那麼快速的手就會繼續盤旋，直到小手進入該圈，然後快手最終趕上小手。

好的，對於最後一部分，手錶的形象並不好，但我希望你明白了。

來源

2017-04-14 06:00:27 Andreas

這是否適用於所有**速度的指針？也就是說，一次慢速移動2次，並且一次快速移動6次？或者一次慢速移動1，一次快速移動17？他們**必須趕上它的通告？ – user7487099

@ user7487099是的。正如我所說，快手抓住慢手的速度取決於速度的差異，但它會趕上。他們都可以在同一圈內以不同的速度行進，而不會偶爾遇到。 – Andreas

@Andreas我懷疑，正如其他答案所提到的，兩個指針應該是可以同步的，這樣如果他們使用正確（錯誤）的跳轉大小，它們將永遠不會實際命中。 –

該證據並不像看起來那麼明顯。

實際上，只需稍作改動，可以使快速指針更快，例如使用fast = fast.next.next.next，算法不再保證工作。

重要的是兩個指針的相對速度。

在標準的情況下，相對速度是2 - 1 = 1，這意味着在每一步，快速指針獲得一個靠近慢指針的單位。通過這種方式，可以保證最快的一個會趕上而不會跳過另一個。

否則，例如如果相對速度是3 - 1 = 2，那麼它們可能不會相交。如果我們從指針之間的奇數距離開始並且週期長度是偶數，就會發生這種情況。在這種情況下，距離總是保持奇數（因此它永遠不會爲零）。

要清楚，如果不小心對速度差指針可能不相交，考慮速度3快速指針，一個緩慢的指針與速度1，在一個週期有4個節點上運行，標記爲0,1,2,3，形成如此的循環0→1→2→3→0.

假設最初，慢指針位於節點0，快指針位於節點（注意，這不是一個強有力的假設，並且不能通過不同的初始化策略來緩解 - 無論初始化方法如何，可能情況是圖中有一些額外的節點，而不是週期的一部分，使指針成爲可能的任意位置y位置，一旦他們都達到了週期）。

經過k步後，慢指針將位於節點k mod 4。快節點將位於節點(1 + 3k) mod 4。假設有一個k，使得快指針和慢指針處於相同的位置，這意味着(1 + 3k) mod 4 = k mod 4,，即(1 + 2k) mod 4 = 0。但左側是一個奇數，因此它不能爲零。因此，指針可指向同一節點的假設導致矛盾。

來源

2017-04-14 06:09:16 qwertyman

那麼，asrereas提到看看手錶，但如果這仍然沒有意義，使this可以幫助。

此外，您還可以簡化您的代碼位：

public boolean isCyclic(Node first) { 
    if(first == null) { 
     return false; 
    } 
    Node fast = first; 
    Node slow = first; 
    while(fast.getNext() != null && fast.getNext().getNext() != null) { 
     slow = slow.getNext(); 
     fast = fast.getNext().getNext(); 
     if(slow == fast) { 
     return true; 
     } 
    } 
    return false; 
}

代碼從http://codecramp.com/linked-list-loop-detection/

複製我也認爲你應該頭初始化快速指針而不是head.next

來源

2017-04-14 06:28:16 EMM

圓形鏈表邏輯

回答

相關問題