Есть произвольный односвязный список, в котором может быть петля, необходимо предложить алгоритм который бы позволил определить, есть ли цикл в O(1) по памяти.
Не то, что бы эта задача была сложной, но она по своему довольно интересна. Ниже приведено два подхода к решению этой задачки. Первое из них является классическим решением, второй подход пораждён мои больным сознанием по мотивам решения задачки по Обходу бинарного дерева с константным количеством памяти.
Подход правильный.
При анализе того, как решить эту задачу очень быстро приходишь к мысли, что необходимо где-то в списке оставить маркер, который позволит понять, что мы в этом узле уже были. Очень быстро становится очевидно, что нет никакой возможности оставить маркер гарантированно на одном из улов петли. Решить эту проблему можно следующим образом: пустить по систем в параллель несколько маркеров с разной скоростью. Таким образом, более быстрый маркер должен дойти дойти либо до конца списка, либо рано или поздно догнать медленный маркер.
Реализация на С:
Реализация на Haskell. Собственно как и практически всегда у меня этим языком - первая мысль: "А как это вообще сделать?", вторая: "Так очевидно же как...".
Подход не правильный, но работающий.
Этот подход основывается на предпосылки - данные можно изменять. Идея следующая, проходим список вперёд разворачивая его. Если конец списка совпадёт с головой - значит была петля. Повторная проходка позволит восстановить исходную структуру данных. Реализация на C (только функция проверки):
Не то, что бы эта задача была сложной, но она по своему довольно интересна. Ниже приведено два подхода к решению этой задачки. Первое из них является классическим решением, второй подход пораждён мои больным сознанием по мотивам решения задачки по Обходу бинарного дерева с константным количеством памяти.
Подход правильный.
При анализе того, как решить эту задачу очень быстро приходишь к мысли, что необходимо где-то в списке оставить маркер, который позволит понять, что мы в этом узле уже были. Очень быстро становится очевидно, что нет никакой возможности оставить маркер гарантированно на одном из улов петли. Решить эту проблему можно следующим образом: пустить по систем в параллель несколько маркеров с разной скоростью. Таким образом, более быстрый маркер должен дойти дойти либо до конца списка, либо рано или поздно догнать медленный маркер.
Реализация на С:
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> struct List { struct List *next; int value; }; struct List* makeList(int all, int inLoop) { struct List *head = malloc(sizeof(struct List)); struct List *current = head; int marker = 1; for (int i = 0; i < all - inLoop; ++i) { current = current->next = malloc(sizeof(struct List)); current->value = marker++; } if (inLoop > 0) { struct List *loopStart = current; for (int i = 0; i < inLoop; ++i) { current = current->next = malloc(sizeof(struct List)); current->value = marker++; } current->next = loopStart->next; } return head; } bool loopInList(struct List *head) { struct List *fastMarker, *slowMarker; fastMarker = slowMarker = head; if (fastMarker->next == NULL) return true; else fastMarker = fastMarker->next; while (true) { if (fastMarker->next == NULL || fastMarker->next->next == NULL) return false; if (fastMarker->next == slowMarker || fastMarker->next->next == slowMarker) return true; fastMarker = fastMarker->next->next; slowMarker = slowMarker->next; } } int main(int argc, char** argv) { struct List * head = makeList(10, 0); printf("%s", loopInList(head) ? "true" : "false"); return 0; }
Реализация на Haskell. Собственно как и практически всегда у меня этим языком - первая мысль: "А как это вообще сделать?", вторая: "Так очевидно же как...".
makeList all inLoop = [1 .. (all - inLoop)] ++ loopListPart where loopListPart | inLoop > 0 = [(all - inLoop + 1) .. all] ++ loopListPart | otherwise = [] list = makeList 5000000 500000 loopInList list@(x:xs) = fastMarker list xs where slowMarker (_:slows) fast = fastMarker slows fast fastMarker _ [] = False fastMarker _ (_:[]) = False fastMarker allSlow@(slow:_) (fast1:fast2:fasts) | fast1 == slow || fast2 == slow = True | otherwise = slowMarker allSlow fasts main = putStrLn $ show $ loopInList list
Подход не правильный, но работающий.
Этот подход основывается на предпосылки - данные можно изменять. Идея следующая, проходим список вперёд разворачивая его. Если конец списка совпадёт с головой - значит была петля. Повторная проходка позволит восстановить исходную структуру данных. Реализация на C (только функция проверки):
bool loopInList(struct List *head) { struct List *current = head, *last = head, *next; current = last = head; if (current->next == NULL) return true; else { current = current->next; last->next = NULL; } while (current->next != NULL) { printf("%d ", current->value); next = current->next; current->next = last; last = current; current = next; } if (current == head) return true; else return false; }
