檢查鏈接列表是否加入回去開始

我試圖檢查鏈表是否指向頭部的最後一個節點。此代碼似乎給出了問題的積極結果，但也給包含指向非頭節點的節點的列表提供了誤報。檢查鏈接列表是否加入回去開始

我一直在嘗試不同的東西，如檢查緩慢的節點是否等於回報真正的頭，但似乎並不奏效。

public boolean isLinkedToStart(Node head) { 
    if (head == null) { 
     return false; 
    } 
    Node fast = head.next; 
    Node slow = head; 
    while (fast != null && fast.next != null) { 
     if (fast.next.next == slow) { 
      return true; 
     } 
     fast = fast.next.next; 
     slow = slow.next; 
    } 
    return false; 
}

有什麼建議嗎？

來源

2013-10-18 sff

該算法（俗稱[Tortoise and Hare]（http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare）算法）是一種通用循環檢測算法，如果鏈表包含**任意**循環，不一定是指向頭部的那個循環，你想要的是一個更具體的變體， – Santa

是以任何特殊的/可識別的方式定義的頭部？ –

頭部是'頭部' – Santa

public boolean isLinkedToStart(Node head) { 
    if (head == null) { 
     return false; 
    } 
    Node fast = head.next; 
    Node slow = head; 
    while (fast != null && fast.next != null) { 
     fast = fast.next.next; 
     slow = slow.next; 
     if(slow.next == head) 
      return true; 
     if (fast == slow) 
      return false; 
    } 
    return false; 
}

好吧，第三次是魅力。

如果在慢速前進之前發現一個循環，那麼我們找到了一個不同的循環。如果緩慢讓它頭頂，那麼這個週期就要開始了。

來源

2013-10-18 18:44:30 Cruncher

你是第一個提到「Floyd Cycle Finding Algorithm」的人。 – Kayaman

哦，我的壞...我想我誤解了這個問題。刪除其他評論。 – vidit

我想這將無限循環的情況下，他得到了一個假陽性 – Cruncher

public boolean isLinkedToStart(Node head) { 
    if (head == null) { 
     return false; 
    } 
    Node probe = head.next; 
    while (probe != null) { 
     if (probe == head) { 
      return true; 
     } 
     if(probe.seen) { 
      return false; 
     } 

     probe.seen = true; 
     probe = probe.next; 
    } 
    return false; 
}

你可以修改你的節點結構嗎？也就是說，你可以添加類似於node.seen == false的東西，然後在循環時切換它，然後修改此代碼^以檢查以確保節點在循環時看不見，並且如果它遇到「已見」節點則返回false？（已在上面實現）

來源

2013-10-18 18:45:29

檢查鏈接列表是否加入回去開始

回答

相關問題