Как я могу найти, является ли связанный список циклическим или циклическим? Я попытался выполнить поиск, но не смог найти удовлетворительного решения. Если возможно, можете ли вы предоставить псевдокод или реализацию Java?
Например: 1 → 3 → 5 → 71 → 45 → 7 → 5, где второй 5 фактически является третьим элементом списка.
Стандартный ответ состоит в том, чтобы взять два итератора в начале, прирастить первый один раз, а второй - дважды. Проверьте, указывают ли они на один и тот же объект. Затем повторяйте до тех пор, пока тот, который увеличивается в два раза, не достигнет первого или не достигнет конца.
Этот алгоритм находит любую круговую ссылку в списке, а не только полный круг.
Псевдокод (не Java, непроверенный - с верхней части моей головы)
bool hasCircle(List l)
{
Iterator i = l.begin(), j = l.begin();
while (true) {
// increment the iterators, if either is at the end, you're done, no circle
if (i.hasNext()) i = i.next(); else return false;
// second iterator is travelling twice as fast as first
if (j.hasNext()) j = j.next(); else return false;
if (j.hasNext()) j = j.next(); else return false;
// this should be whatever test shows that the two
// iterators are pointing at the same place
if (i.getObject() == j.getObject()) {
return true;
}
}
}
Простой алгоритм под названием алгоритм Флойда должен иметь два указателя a и b, которые начинаются с первого элемента в связанном списке. Затем на каждом шаге вы увеличиваете один раз и b два раза. Повторяйте до тех пор, пока вы не достигнете конца списка (нет цикла) или == b (связанный список содержит цикл).
Другим алгоритмом является алгоритм Brent.
Три основных стратегии, о которых я знаю:
Запуск перехода по списку и отслеживание всех узлов, которые вы посетили (например, для хранения их адресов на карте). Каждый новый node, который вы посещаете, проверьте, если вы уже посетили его. Если вы уже посетили node, тогда, очевидно, будет цикл. Если нет цикла, вы в конце концов достигнете конца. Это не очень удобно, поскольку сложность O (N) пространства для хранения дополнительной информации.
Решение черепахи/зайца. Начните два указателя в начале списка. Первый указатель "Черепаха" перемещается на одну итерацию на каждую node. Другой указатель, "Заяц", перемещает два узла на каждую итерацию. Если нет петли, заяц и черепаха оба достигнут конца списка. Если есть петля, Заяц передаст Черепаху в какой-то момент, и когда это произойдет, вы знаете, что есть петля. Это O (1) пространственная сложность и довольно простой алгоритм.
Используйте алгоритм для обращения к связанному списку. Если в списке есть цикл, вы вернетесь в начале списка, пытаясь отменить его. Если у него нет цикла, вы закончите его реверсирование и попадете в конец. Это O (1) пространственная сложность, но немного уродливый алгоритм.
Я посчитаю ваши узлы и снова вернусь к * head.
Используйте алгоритм Черепаха-Харе.
Как насчет следующего подхода:
Сортируйте список ссылок в порядке возрастания, следуя любым стандартным алгоритмам. Перед сортировкой: 4-2-6-1-5 После Сортировка: 1-2-4-5-6
После сортировки проверьте для каждого node данные и сравните их с данными node, примерно так:
if (currentcode- > data > currentnode- > link- > data) т.е. round = true;
При любом сравнении, если какой-либо из "currentnode- > data" больше, чем "currentcode- > link- > data" для отсортированного списка ссылок, это означает, что текущий node указывает на предыдущий node (т.е. круговой);
Ребята, у меня нет настройки для проверки кода. Сообщите мне, если это понятие работает.
Начните с одного node и запишите его, затем перейдите по всему списку, пока не достигнете нулевого указателя или node, с которого вы начали.
Что-то вроде:
Node start = list->head;
Node temp = start->next;
bool circular = false;
while(temp != null && temp != start)
{
if(temp == start)
{
circular = true;
break;
}
temp = temp->next;
}
return circular
Это O (n), что в значительной степени является лучшим, что вы сможете получить с единственным списком (исправьте меня, если я ошибаюсь).
Чтобы найти какие-либо циклы в списке (например, в середине), вы можете сделать:
Node[] array; // Use a vector or ArrayList to support dynamic insertions
Node temp = list->head;
bool circular = false;
while(temp != null)
{
if(array.contains(temp) == true)
{
circular = true;
break;
}
array.insert(temp);
temp = temp->next;
}
return circular
Это будет немного медленнее из-за времени вставки динамических массивов.
@samoz имеет в моей точке зрения ответ! Отсутствует псевдокод. Будет что-то вроде
ваш список - это ваш список контактов
allnodes = hashmap
while yourlist.hasNext()
node = yourlist.next()
if(allnodes.contains(node))
syso "loop found"
break;
hashmap.add(node)
Извините, код очень псевдо (теперь делайте больше скриптов, а затем java)
Вот хороший сайт, на котором можно копировать различные решения.
Это победитель на этом сайте
// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}
Это решение - "Floyd's Циклический алгоритм поиска" в "Недетерминированных алгоритмах" Роберт В. Флойд в 1967 году. "Черепаха и зайчик" Алгоритм".
Он никогда не завершится из цикла, это также можно сделать в следующем решении:
bool hasCircle(List l)
{
Iterator i = l.begin(), j = l.begin();
while (true) {
// increment the iterators, if either is at the end, you're done, no circle
if (i.hasNext()) i = i.next(); else return false;
// second iterator is travelling twice as fast as first
if (j.hasNext()) j = j.next(); else return false;
if (j.hasNext()) j = j.next(); else return false;
// this should be whatever test shows that the two
// iterators are pointing at the same place
if (i.getObject() == j.getObject()) {
return true;
}
if(i.next()==j)
break;
}
}
Алгоритм:
Попробуйте это
/* Link list Node */
struct Node { int данные; struct Node * next; };
/* Эта функция возвращает true, если задано связанное list - круговой, иначе false. */ bool isCircular (struct Node * head) { // Пустой связанный список является круглым if (head == NULL) return true;
// Next of head
struct Node *node = head->next;
// This loop would stope in both cases (1) If
// Circular (2) Not circular
while (node != NULL && node != head)
node = node->next;
// If loop stopped because of circular
// condition
return (node == head);
}