Как определить, имеет ли связанный список цикл, используя только два расположения памяти

Кто-нибудь знает об алгоритме, чтобы найти, если привязанный список петли сам по себе, используя только две переменные для перемещения по списку. Скажем, у вас есть связанный список объектов, неважно, какой тип объекта. У меня есть указатель на заголовок связанного списка в одной переменной, и мне предоставляется только одна переменная для перемещения по списку.

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

Ответы

Ответ 1

Я бы предложил использовать Floyd Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm. Он имеет сложность O (n), и я думаю, что он соответствует вашим требованиям.

Пример кода:

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Дополнительная информация о Wikipedia: Алгоритм поиска циклов Floyd.

Ответ 3

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

Начните с указателя "slow" и "fast", указывающего на любое место в списке. Запустите цикл обхода. Если "быстрый" указатель в любой момент совпадает с медленным указателем, у вас есть круговой связанный список.

int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}

Ответ 4

Я попытался решить это сам и нашел другое (менее эффективное, но все же оптимальное) решение.

Идея основана на обратном объединении списка в линейном времени. Это можно сделать, выполнив две свопы на каждом этапе итерации по списку. Если q - это предыдущий элемент (изначально нуль), а p - текущий, то своп (q, p- > next) swap (p, q) приведет к обратному соединению и продвижению двух указателей одновременно. Сделки могут быть выполнены с помощью XOR, чтобы не было необходимости использовать третью ячейку памяти.

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

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

Ответ 5

int isListCircular(ListNode* head){
    if(head==NULL)
        return 0;
    ListNode *fast=head, *slow=head;
    while(fast && fast->next){
        if(fast->next->next==slow)
            return 1;
        fast=fast->next->next;
        slow=slow->next;
    }
    return 0;
}

Ответ 6

Принятие этой проблемы на следующем шаге будет определять цикл (то есть не только цикл существует, но и где именно он находится в списке). Алгоритм Черепаха и Харе можно использовать для одного и того же, однако нам потребуется постоянно следить за заголовком списка. Иллюстрацию этого алгоритма можно найти здесь.

Ответ 7

boolean findCircular(Node *head)
{
Node *slower, * faster;
slower = head;
faster = head->next;
while(true) {


 if( !faster || !faster->next)
   return false;

 else if (faster == slower || faster->next == slower)
    return true;
 else{

    faster = faster->next->next;
   }
}
}