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

Question

Какой лучший (остановочный) алгоритм для определения наличия в связанном списке цикла?

[Редактировать] Анализ асимптотической сложности как по времени, так и по пространству был бы приятен, поэтому ответы можно было бы сравнить лучше.

[Редактировать] Первоначальный вопрос не касался узлов с outdegree> 1, но есть некоторые разговоры об этом. Этот вопрос больше похож на «Лучший алгоритм обнаружения циклов в ориентированном графе».

Answer 1

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

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

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

Answer 2

Взять 2 указателя * p и * q, начать обход связанного списка «LL», используя оба указателя:

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

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

Условия:

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

2) оба указателя указывают на ноль: никакого цикла нет

Answer 3

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

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

1. Держите счетчик при обходе размера списка.

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

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

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

Answer 4

def has_cycle (head): counter = set ()

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

Answer 5

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

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

Answer 6

Решение Hack (должно работать на C / C ++):

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

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

Answer 7

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

Пример кода ниже реализован в соответствии с этим решением. Более быстрый указатель - 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;
}

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

Answer 8

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

Answer 9

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

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

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

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

Answer 10

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

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