在java中打破一個循環鏈表和尋找複雜

-1

我必須找出一個鏈表循環，我已經找到了使用烏龜和野兔的解決方案如下在java中打破一個循環鏈表和尋找複雜

boolean hasLoop(Node first) { 

    if(first == null) // list does not exist..so no loop either. 
     return false; 

    Node slow, fast; // create two references. 

    slow = fast = first; // make both refer to the start of the list. 

    while(true) { 

     slow = slow.next;   // 1 hop. 

     if(fast.next != null) 
      fast = fast.next.next; // 2 hops. 
     else 
      return false;   // next node null => no loop. 

     if(slow == null || fast == null) // if either hits null..no loop. 
      return false; 

     if(slow == fast) // if the two ever meet...we must have a loop. 
      return true; 
    } 
}

，現在我的問題是如何能我檢測循環的開始，以及如何計算程序的複雜度，就像增加列表的大小一樣。指針遇到的點不會增加列表大小的比例。

來源

2013-10-19 ankit

下來選民，你可以告訴的原因 – ankit

開裂的編碼訪談：

試想一下，作爲一個比喻，兩個人在跑道上賽跑，一個運行快兩倍，其他。如果他們在同一個地方出發，他們下次什麼時候會見？接下來他們將在下一圈開始時相遇。

現在，讓我們假設快跑者在第n圈時有一個k米的開局。他們下次什麼時候見面？他們將在下一圈開始前達到k米。（爲什麼？快跑者會做出k + 2（n-k）個步驟，包括它的開始，慢跑者會做出n-k個步驟，兩者在循環開始之前都會有k個步驟。）

現在，回到問題，當快速跑者（n2）和慢跑者（n1）在我們的循環鏈表上移動時，當n1進入時，n2將在循環中有一個開始。具體來說，它將具有k的開頭，其中k是循環之前的節點的數量。由於n2具有k個節點的頭部起點，因此n1和n2將在循環開始之前遇到k個節點。

所以，我們現在知道以下幾點：

頭從環路啓動（定義）個節點。
MeetingPoint for n1和n2是來自LoopStart的k個節點（如上所示）。

因此，如果我們將n1移回Head並在MeetingPoint保留n2，並以相同的速度移動它們，它們將在LoopStart處相遇。

LinkedListNode FindBeginning(LinkedListNode head) 
{ 
    LinkedListNode n1 = head; 
    LinkedListNode n2 = head; 
    // Find meeting point 
    while (n2.next != null) 
    { 
     n1 = n1.next; 
     n2 = n2.next.next; 
     if (n1 == n2) 
     { 
      break; 
     } 
    } 

    // Error check - there is no meeting point, and therefore no loop 
    if (n2.next == null) 
    { 
     return null; 
    } 

    /* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps 
    /* from the Loop Start. If they move at the same pace, they must 
    * meet at Loop Start. */ 
    n1 = head; 
    while (n1 != n2) 
    { 
     n1 = n1.next; 
     n2 = n2.next; 
    } 
    // Now n2 points to the start of the loop. 
    return n2; 
}

來源

2013-10-19 07:57:56

如果沒有循環，那麼你的代碼將在Θ(n)因爲你跳至少n次，最多3/2*n時間執行。

如果存在循環，那麼以圖論的術語來說，它是一個長度最多爲n的循環。週期中的fast和slow之間的距離每跳都精確地變化1，因此它們在進入循環之前跳至最多n次，直到它們相遇。他們都在最多n-1跳之後進入循環，所以這會給你帶來最差的複雜度。

[for循環最好的情況複雜O(1)，因爲你可以立即進入循環，恆定的跳數後的意思，所以這是不是很有趣。]

來源

2013-10-19 11:48:10

在java中打破一個循環鏈表和尋找複雜

回答

相關問題