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

Question

Недавно меня попросили на собеседовании для разработки алгоритма, который может определить, является ли связанный список циклическим. Поскольку это связанный список, мы не знаем его размера. Это двусвязный список, где каждый узел имеет указатели «следующий» и «предыдущий». Узел может быть связан с любым другим узлом или он может быть связан с самим собой.

Единственное решение, которое я нашел в то время, - это выбрать узел и проверить его со всеми узлами в связанном списке. Интервьюеру явно не понравилась идея, так как это не оптимальное решение. Что было бы лучше?

Answer 1

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

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

Answer 2

Общее решение состоит в том, чтобы 2 указателя двигались с разной скоростью. В конечном итоге они будут равны, если некоторая часть списка будет круглой. Что-то вроде этого:

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

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

     slowNode = slowNode.next();
   }
   return false;
 }

явно украдено отсюда: http://ostermiller.org/find_loop_singly_linked_list.html

Answer 3

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

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

Answer 4

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

 - -*- \
     \  \
      \---

На узле * есть 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.
 }

Answer 5

Вот простой подход к тестированию, если в связанном списке есть циклы (если он циклический), основанный на алгоритме Флойда:

int HasCycle(Node* head)
{
    Node *p1 = head;
    Node *p2 = head;

  while (p1 && p2) { 
        p1 = p1->next;
        p2 = p2->next->next;

        if (p1 == p2)
            return 1;
    }
    return 0;
}

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

Answer 6

Невероятно, насколько широко могут распространяться сложные решения.

Вот абсолютный минимум, необходимый для определения того, является ли связанный список круговым:

bool is_circular(node* head)
{
    node* p = head;

    while (p != nullptr) {
        p = p->next;
        if (p == head)
            return true;
    }

    return false;
}

Answer 7

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

Answer 8

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

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

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

Answer 9

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

Это список двойных ссылок, каждый узел имеет указатели 'next' и 'previous'.

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

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

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

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

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

Если у нас есть такой случай, как: 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 итераций.

Answer 10

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