Q

檢測鏈接列表中的循環

2011-10-09 163 views 3 likes

3

如何使用單個指針檢測鏈接列表中的循環？（不希望慢速和快速指針（野兔和烏龜））檢測鏈接列表中的循環

2011-10-09 Ashish Anand

+0

如果答案是兔子和烏龜算法，那已經是一個非常人爲的問題了。 –

+0

「只使用單個指針」是什麼意思？您已經使用一個指針存儲了一個指向列表頭部的指針;你被允許做出除此之外的任何指針嗎？ – templatetypedef

+0

@templatetypedef：兩個指針只能在這裏表示：兩個指針訪問鏈表。 – false

A

回答

1

如果您不介意額外的O（N）內存，您可以使用hastable來存儲訪問節點，。

在每個節點上，檢查散列表中是否已存在該節點。如果是這樣，你找到了一個循環。否則，將其添加到散列表並轉到下一個節點。

2011-10-09 19:06:08 MAK

+0

但是這不需要多個指針（散列表中存儲的每個節點都有一個指針？） – templatetypedef

+0

@templatetypedef：True。我閱讀「使用單個指針」作爲含義使用單個指針遍歷列表，而不是使用兩個指針。這在迭代中使用了單個指針，但是我們仍然存儲指向所有訪問的節點的指針 - 因此我在我的答案中提到了O（n）內存。我覺得OP可能沒問題。 – MAK

0

如果您的節點由值和指向下一個節點的指針組成，您可以使用列表創建一個指向第一個節點的指針。您可以在每個節點上檢查指針是否具有與指向第一個節點的指針相同的值。

2011-10-09 19:11:51

+1

如果循環迴轉到列表中間而不是前面？ – templatetypedef

1

Brent's algorithm顯然是最好的：對於無循環列表，只需訪問列表一次，而弗洛伊德的烏龜和野兔需要重新訪問一半節點。對於包含循環的列表，它永遠不會在循環中「旋轉」得比Floyd長;而在最好的情況下只需要一個週期，當弗洛伊德需要很多。想想一個長循環的序列，然後是一個長度爲1的循環。在這種情況下，布倫特最好的情況是在循環訪問一次後檢測循環 - 因此只需訪問一次節點;而Floyd必須平均訪問每個節點三次。

其基本思想是訪問鏈表，並將當前節點的指針與一個已經訪問過的節點進行比較。也就是說，每個訪問節點的一個指針比較。指針隨時按照簡單的邏輯進行更新。

2013-01-07 00:53:13 false

+0

這不需要兩個指針嗎？ – templatetypedef

+0

@templatetypedef：只有一個指針在鏈表中篩選。另一個設置爲第一個值。 – false

相關問題