Лучший алгоритм проверки, если связанный список имеет цикл

Ответ 1

У вас есть два указателя, повторяющихся в списке; проведите один проход в два раза быстрее, чем другой, и сравните свои позиции на каждом шаге. С головы, что-то вроде:

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There a cycle"); }
    tortoise = tortoise->next;
}

O (n), что так хорошо, как вы можете получить.

Ответ 2

Предварительное условие: отслеживайте размер списка (обновляйте размер, если добавлен или удален node).

Обнаружение петли:

• Держите счетчик при перемещении по размеру списка.

• Если счетчик превышает размер списка, существует возможный цикл.

Сложность: O (n)

Примечание. Сравнение между счетчиком и размером списка, а также операция обновления размера списка должны быть потокобезопасными.

Ответ 3

Возьмите 2 указателя * p и * q, начните перемещение связанного списка "LL" с помощью обоих указателей:

1) указатель p будет удалять предыдущий node каждый раз и указывать на следующий node.

2) указатель q будет идти каждый раз только в прямом направлении.

условия:

1) указатель p указывает на null и q указывает на некоторый node: присутствует Loop

2) оба указателя, указывающие на null: no loop is

Ответ 4

Как использовать хэш-таблицу для хранения уже увиденных узлов (вы смотрите на них по порядку с самого начала списка)? На практике вы могли бы достичь чего-то близкого к O (N).

В противном случае использование сортированной кучи вместо хэш-таблицы приведет к достижению O (N log (N)).

Ответ 5

Интересно, есть ли другой способ, чем просто итеративно - заполнить массив при переходе вперед и проверить, присутствует ли текущий node в массиве...

Ответ 6

Алгоритм Конрада Рудольфа не будет работать, если цикл не указывает на начало. Следующий список сделает его бесконечным циклом: 1- > 2- > 3- > 2.

Алгоритм DrPizza - это, безусловно, путь.

Ответ 7

В этом случае код OysterD будет самым быстрым решением (раскраска вершин)

Это меня действительно удивило бы. Мое решение делает не более двух проходов по списку (если последний node связан с предпоследним номером), а в общем случае (без цикла) будет выполняться только один проход. Без хеширования, выделения памяти и т.д.

Ответ 8

В этом случае код OysterD будет самым быстрым решением (раскраска вершин)

Это меня действительно удивило бы. Мое решение делает не более двух проходов по списку (если последний node связан с предпоследним номером), а в общем случае (без цикла) будет выполняться только один проход. Без хеширования, выделения памяти и т.д.

Да. Я заметил, что формулировка не была идеальной и перефразировала ее. Я все еще верю, что умное хеширование может ускориться - волосами. Я считаю, что ваш алгоритм является лучшим решением.

Чтобы подчеркнуть мою точку зрения: окраска vertec используется для обнаружения циклов в зависимостях современными сборщиками мусора, поэтому для этого существует очень реальный прецедент. В основном они используют битовые флаги для выполнения раскраски.

Ответ 9

Вам нужно будет посетить каждый node, чтобы определить это. Это можно сделать рекурсивно. Чтобы остановить посещение уже посещаемых узлов, вам нужен флаг, чтобы сказать "уже посещенный". Это, конечно, не дает вам циклов. Поэтому вместо битового флага используйте число. Начните с 1. Проверьте подключенные узлы, а затем отметьте их как 2 и запишите до тех пор, пока сеть не будет закрыта. Если при проверке узлов вы сталкиваетесь с node, который более чем на один меньше текущего node, тогда у вас есть цикл. Длина цикла определяется разницей.

Ответ 10

Два указателя инициализируются в начале списка. Один указатель вперед один раз на каждом шаге, а другой - дважды вперед на каждом шаге. Если более быстрый указатель снова встречает медленный, в списке есть цикл. В противном случае нет цикла, если более быстрый достигнет конца списка.

Ниже приведен пример кода ниже в соответствии с этим решением. Более быстрый указатель - pFast, а медленнее - pSlow.

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

Это решение доступно на в моем блоге. В блоге обсуждается больше проблем: что такое запись node, когда в списке есть цикл/цикл?

Ответ 11

"Hack" (должно работать на C/С++):

• Перейдите к списку и установите последний бит указателя next равным 1.
• Если вы найдете элемент с помеченным указателем - верните true и первый элемент цикла.
• Прежде чем возвращать, reset указывает назад, хотя я считаю, что разыменование будет работать даже с отмеченными указателями.

Сложность времени - 2n. Похоже, что он не использует временные переменные.

Ответ 12

Это решение, использующее таблицу Hash (только список), чтобы сохранить адрес указателя.

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False

Ответ 13

def has_cycle (head): counter = set()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next