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

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

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

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

<Ол>

Сохраняйте счетчик при обходе размера списка.

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

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

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

Answer 3

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

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

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

условия:

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

2) оба указателя указывают на null:никакой петли там нет

Answer 4

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

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

Answer 5

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

Answer 6

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

Алгоритм DrPizza - определенно правильный путь.

Answer 7

  

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

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

Answer 8

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

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

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

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

Answer 9

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

Answer 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;
}

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

Answer 11

"Хакерское" решение (должно работать на C / C ++):

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

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

Answer 12

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

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

Answer 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