正確，但無法檢測到多種循環鏈表

Question

我要在以下情況下

1-2-3-4-5 
|----------| ===> case 1 

1-2-3-4-5 
|-------| ===> case 2 

檢測迴路如果1個週期檢測算法適用於情況2 我做了案例2空轉我發現野兔指針正常結束。 此外，我認爲情況2是無效的單鏈表，因爲它包含2個下一個指針。 我的假設對於案例2是否正確？ 整個場景是單鏈表嗎？

Answer 1

我會根據一系列有關你所問的假設給出答案。

我猜你的格式化搞砸了，你正在使用一個單一鏈接列表建立一個節點結構，有一個指針稱爲「下一個」。

我還假設您有一個指向名爲Root的第一個元素的指針。

接下來，我假設您的算法包含存儲根的副本，然後遍歷列表以查看是否返回根。

這將在等的情況下工作：

A -> B -> C -> D -> E //and E -> A. 

但是，通過添加一個新的，如果

A -> B -> C -> D -> E //and E -> B. 

一種方法是標記每個節點訪問，當您走是行不通的字段放入結構中，或保留一個hashTable，然後查看是否有重複元素。 （您實際上可以將每個第十個節點添加到散列表中，但是檢查每個訪問節點是否與散列表重複）。

如果您事先知道鏈接列表中有多少元素（並且沒有被修改），那麼簡單地走多次並查看下一個節點是否爲空。

Answer 2

這裏是週期檢測用的解決方案，它不涉及分配堆內存：

struct Node { 
    int val; 
    struct node * next; 
}; 

bool containsCycle(Node * head) 
{ 
    Node * walker = head; 
    NOde * fastWalker = head; 
    while(walker && fastWalker) 
    { 
     fastWalker = fastWalker->next; 
     if(walker == fastWalker) 
     return true; 
     if(fastWalker) 
     fastWalker = fastWalker->next; 
     if(walker == fastWalker) 
     return true; 
     walker = walker->next; 
    } 
    // Fell out of the loop, no cycle 
    return false; 
} 

該算法使用兩個指針即預先以不同的速度。如果列表中有一個循環，則兩個指針在一個點上彼此相等。