Проверка списка на наличие цикла в O(1) по памяти

Есть произвольный односвязный список, в котором может быть петля, необходимо предложить алгоритм который бы позволил определить, есть ли цикл в O(1) по памяти.

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

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

Реализация на С:

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