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

голоса
43

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

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

Задан 30/01/2009 в 08:51
источник пользователем
На других языках...                            


7 ответов

голоса
45

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

Более подробная информация о Википедии: цикл ознакомительного алгоритм Флойд .

Ответил 30/01/2009 в 09:01
источник пользователем

голоса
17

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

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

Ответил 30/01/2009 в 08:55
источник пользователем

голоса
9

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

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

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
}
Ответил 30/01/2009 в 08:55
источник пользователем

голоса
3

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

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

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

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

Ответил 05/05/2009 в 18:52
источник пользователем

голоса
2
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;
}
Ответил 09/05/2012 в 21:21
источник пользователем

голоса
0
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;
   }
}
}
Ответил 03/09/2015 в 14:59
источник пользователем

голоса
0

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

Ответил 11/01/2014 в 21:15
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more