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: 
C, non-golfed
-------------

The idea is to have to pointers p1 and p2 that traverse the list. p2 moves twice as fast as p1. If p2 reaches p1 at some point then there is a loop. Here is the C code (not tested, though).

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

int has_loops(struct node *p)
{
  struct node *p1 = p, *p2 = p->next;
  if (!p2) return 0;

  while (p1 != p2) {
    // p1 goes one step
    p1 = p1->next;
    if (!p1) return 0;

    // p2 goes two steps
    p2 = p2->next;
    if (!p2) return 0;
    p2 = p2->next;
    if (!p2) return 0;
  }

  return 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

```