Это звучит как случай, когда вы, наконец, можете применить этот вопрос о пустяках интервью: найдите цикл в связанном списке, используя только O (1) памяти.
В этом случае ваш «связанный список» - это последовательность элементов, которую вы перечисляете. Используйте два перечислителя, запустите один на половинной скорости, и если быстрый когда-нибудь попадет в медленный, у вас будет цикл. Это также будет время O (n) вместо времени O (n ^ 2), необходимого для проверки «видимого» списка. Недостатком является то, что вы узнаете о цикле только после того, как некоторые узлы были обработаны несколько раз.
В этом примере я заменил метод «половинной скорости» более простым для записи методом «маркеров сброса».
class GenTreeNode {
...
///<summary>Wraps an the enumeration of linked data structures such as trees and linked lists with a check for cycles.</summary>
private static IEnumerable<T> CheckedEnumerable<T>(IEnumerable<T> sub_enumerable) {
long cur_track_count = 0;
long high_track_count = 1;
T post = default(T);
foreach (var e in sub_enumerable) {
yield return e;
if (++cur_track_count >= high_track_count) {
post = e;
high_track_count *= 2;
cur_track_count = 0;
} else if (object.ReferenceEquals(e, post)) {
throw new Exception("Infinite Loop");
}
}
}
...
///<summary>Enumerates the tree's nodes, assuming no cycles</summary>
private IEnumerable<GenTreeNode> tree_nodes_unchecked() {
yield return this;
foreach (var child in this.nodes)
foreach (var e in child.tree_nodes_unchecked())
yield return e;
}
///<summary>Enumerates the tree's nodes, checking for cycles</summary>
public IEnumerable<GenTreeNode> tree_nodes()
{
return CheckedEnumerable(tree_nodes_unchecked());
}
...
void ProcessTree() {
foreach (var node in tree_nodes())
proceess(node);
}
}