Циклический алгоритм связанного списка

Хранить хэш значений указателя. Каждый раз, когда вы посещаете узел, хешируйте его указатель и сохраняйте его. Если вы когда-нибудь посетите тот, который уже был сохранен, вы знаете, что ваш список круглый.

Это алгоритм O (n), если ваша хеш-таблица постоянна.

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

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

То, что вы ищете, - это алгоритм поиска цикла. Алгоритм, на который ссылается Джоэл, называется либо алгоритмом «черепаха и заяц», либо алгоритмом поиска цикла Флойда. Я предпочитаю второе, потому что похоже, что из него получится хорошее заклинание D&D.

Обзор алгоритмов поиска циклов в Викпедии с примером кода

Другой вариант состоит в том, что, поскольку список является двусвязным, вы можете пройти по списку и проверить, всегда ли следующие указатели previous являются текущим узлом или нулевым, а не заголовком. Идея здесь в том, что цикл должен охватывать весь список или выглядеть примерно так:

 - -*- \
     \  \
      \---

В Node * есть 2 входящих ссылки, только одна из которых может быть предыдущей.

Примерно так:

 bool hasCycle(Node head){
    if( head->next == head ) return true;

    Node current = head -> next;

    while( current != null && current->next != null ) {
         if( current == head || current->next->prev != current )
            return true;

         current = current->next;
    }
    return false; // since I've reached the end there can't be a cycle.
 }

Начните с двух указателей, указывающих на один и тот же элемент. Перемещение по списку на один указатель после указателей next . Другой просматривает список, следуя указателям previous . Если два указателя встречаются, то список круговой. Если вы найдете элемент с указателем предыдущий или следующий , установленным на NULL , то вы знаете, что список является , а не круговым.

[Изменить формулировку вопроса и темы, чтобы уточнить, что мы проверяем циклы в двусвязном списке, а не проверяем, является ли двусвязный список просто круговым, поэтому части этого сообщения может быть неуместным.]

Это список с двойной связью с каждым узлом с указателями «следующий» и «предыдущий».

Двусвязные списки обычно реализуются, когда начало и конец списка указывают на NULL, чтобы указать, где они заканчиваются.

[Edit] Как указано, это только проверяет, является ли список круговым в целом, а не циклами в нем, но это была формулировка исходного вопроса. Если список круговой, tail-> next == head и / или head-> prev == tail. Если у вас нет доступа как к хвостовому, так и к головному узлам и есть только один из них, но не оба, тогда достаточно просто проверить, является ли head-> prev! = NULL или tail-> next! = NULL.

Если этого недостаточно, потому что нам дан только какой-то случайный узел [и мы ищем циклы в любом месте списка], то все, что вам нужно сделать, это взять этот случайный узел и продолжать перемещаться по списку, пока не дойдете до совпадающий узел (в этом случае круговой) или нулевой указатель (в этом случае это не так).

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

[Edit] Сейчас мой разум переключился на поиск циклов в списке, а не на определение того, является ли связанный список круговым.

Если у нас есть случай вроде: 1 <-> 2 <-> 3 <-> [2]

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

Конечно, это может быть дешево. Если нам разрешено изменять узлы списка, мы могли бы сохранить флаг простого прохода с каждым узлом, который мы устанавливаем при этом. Если мы встретим узел с уже установленным флагом, значит, мы нашли цикл. Однако это не годится для параллелизма.

Здесь предлагается решение [которое я взял из другого ответа] под названием «Алгоритм поиска цикла Флойда». Давайте посмотрим на него (изменено, чтобы мне было немного легче читать).

function boolean hasLoop(Node startNode)
{
    Node fastNode2 = startNode;
    Node fastNode1 = startNode;
    Node slowNode = startNode;

    while ( slowNode && (fastNode1 = fastNode2.next()) && (fastNode2 = fastNode1.next()) )
    {
        if (slowNode == fastNode1 || slowNode == fastNode2) 
            return true;
        slowNode = slowNode.next();
    }
    return false;
}

Это в основном предполагает использование 3 итераторов вместо 1.Мы можем рассмотреть такой случай: 1-> 2-> 3-> 4-> 5-> 6 -> [2] case:

Сначала мы начинаем с [1] с быстрым итератором до [2] и другой в [3] или [1, 2, 3]. Мы останавливаемся, когда первый итератор совпадает с одним из двух вторых итераторов.

Мы продолжаем с [2, 4, 5] (первый быстрый итератор проходит следующий узел второго быстрого итератора, а второй быстрый итератор проходит следующий узел первого быстрого итератора после этого). Затем [3, 6, 2] и, наконец, [4, 3, 4].

Ура, мы нашли совпадение и, таким образом, определили, что список содержит цикл из 4 итераций.

Предположим, что кто-то говорит: "Здесь указатель на член списка. Является ли он членом кругового списка?", то вы можете исследовать все достижимые члены списка в одном направлении на предмет указателей на один узел, на который вам дали указатель, который должен указывать в сторону от вас. Если вы решили идти в направлении next, то вы ищете указатели next, которые равны указателю, который вам дали первым. Если вы решили идти в направлении prev, то ищите указатели prev, которые равны указателю, который вам дали первым. Если вы достигли указателя NULL в любом направлении, то вы нашли конец и знаете, что он не является круговым.

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

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

Что вам нужно, так это алгоритм Флойда для поиска циклов. Вы также можете думать о нахождении точки пересечения цикла как о домашнем задании.