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

Question

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

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

Answer 1

Я бы предложил использовать Floyd's Cycle-Finding Algorithm aka 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;
}

Дополнительная информация о Википедии: Алгоритм Флойда по нахождению цикла .

Answer 2

Вы можете использовать алгоритм Черепаха и Кролик .

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

Answer 3

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

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

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
}

Answer 4

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

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

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

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

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

Answer 6

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

Answer 7

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