Question: This comes from one of my favorite interview questions, though apparently it is now a fairly well-known puzzle. I have no way of knowing, but if you have already heard the answer it would be polite to let others try instead.

### Task:

Write a function that takes as input a singly-linked list and returns true if it loops back on itself, and false if it terminates somewhere.

Here's some example code in C as a starting point so you can see what I mean, but feel free to write your answer in whatever language you like:

```
struct node
{
    void *value;
    struct node *next;
};

int has_loops(struct node *first)
{
    /* write your own loop detection here */
}

```

### Hints:

There is a way to make this function run in O(n) time with a constant amount of extra memory. Good on you if you figure it out, but any working answer deserves some upvotes in my book.

Answer: 
Since the solution is already in the open, I think it's fair to step in now with Brent's algorithm, which is the one I'm familiar with from integer factorisation.

```
#define bool int
#define false 0
#define true 1

bool has_loops(struct node *first) {
    if (!first) return false;

    struct node *a = first, *b = first;
    int step = 1;

    while (true) {
        for (int i = 0; i < step; i++) {
            b = b->next;
            if (!b) return false;
            if (a == b) return true;
        }

        a = a->next;
        if ((step << 1) > 0) step <<= 1;
    }
}

```
Haskell
-------

Naive algorithm:

```
import Data.Set (Set)
import qualified Data.Set as Set

type Id = Integer
data Node a = Node { getValue :: a, getId :: Id }

hasLoop :: [Node a] -> Bool
hasLoop = hasLoop' Set.empty

hasLoop' :: Set Id => [Node a] -> Bool
hasLoop' set xs = case ns of
  [] -> False
  x:xs' -> let
    ident = getId x
    set' = Set.insert ident set
    in if Set.member ident set
      then True
      else hasLoop' set' xs'

```

Floyd's Cycle-Finding Algorithm:

```
import Control.Monad (join)
import Control.Monad.Instances ()
import Data.Function (on)
import Data.Maybe (listToMaybe)

type Id = Integer
data Node a = Node { getValue :: a, getId :: Id }

next :: [a] -> Maybe [a]
next [] = Nothing
next (_:xs) = Just xs

nexts :: [a] -> [a] -> (Maybe [a], Maybe [a])
nexts xs ys = (next xs, next $ next ys)

hasLoop :: [Node a] -> Bool
hasLoop = uncurry hasLoops' . join nexts 

hasLoop' :: Maybe [Node a] -> Maybe [Node a] -> Bool
hasLoop' (Just xs) (Just ys)
  | on (==) (getId . listToMaybe) xs ys = True
  | otherwise = uncurry hasLoop' $ nexts xs ys
hasLoop' _ Nothing = False
hasLoop' Nothing _ = False -- not needed, but there for case completeness

```