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: 
Ada
---

The "Floyd's Cycle-Finding Algorithm" is the best solution. It's also called "The Tortoise and the Hare Algorithm".

linked\_lists.ads:

```
generic
   type Element_Type is private;
package Linked_Lists is

   type Node is private;
   type List is private;

   function Has_Loops (L : List) return Boolean;

private

   type List is access Node;
   type Node is record
      Value   : Element_Type;
      Next    : List;
   end record;

end Linked_Lists;

```

linked\_lists.adb:

```
package body Linked_Lists is

   function Has_Loops (L : List) return Boolean is
      Slow_Iterator : List := L;
      Fast_Iterator : List := null;
   begin
      -- if list has a second element, set fast iterator start point
      if L.Next /= null then
         Fast_Iterator := L.Next;
      end if;

      while Fast_Iterator /= null loop

         -- move slow iterator one step
         -- guaranteed to be /= null, since it is behind fast iterator
         Slow_Iterator := Slow_Iterator.Next;

         -- move fast iterator one step
         -- guaranteed to be valid, since while catches null
         Fast_Iterator := Fast_Iterator.Next;
         -- move fast iterator another step
         -- null check necessary
         if Fast_Iterator /= null then
            Fast_Iterator := Fast_Iterator.Next;
         end if;

         -- if fast iterator arrived at slow iterator -> loop detected
         if Fast_Iterator = Slow_Iterator then
            return True;
         end if;

      end loop;

      -- fast iterator arrived end, no loop present.
      return False;
   end Has_Loops;

end Linked_Lists;

```

here is the implementation of the Brent algorithm:

```
package body Linked_Lists is

   function Has_Loops (L : List) return Boolean is
      Turtle : List     := L;
      Rabbit : List     := L;
      Steps  : Natural  := 0;
      Limit  : Positive := 2;
   begin

      -- is rabbit at end?
      while Rabbit /= null loop

         -- increment rabbit
         Rabbit := Rabbit.Next;
         -- increment step counter
         Steps := Steps + 1;

         -- did rabbit meet turtle?
         if Turtle = Rabbit then
            -- LOOP!
            return True;
         end if;

         -- is it time to move turtle?
         if Steps = Limit then
            Steps := 0;
            Limit := Limit * 2;
            -- teleport the turtle
            Turtle := Rabbit;
         end if;

      end loop;

      -- rabbit has reached the end
      return False;
   end Has_Loops;

end Linked_Lists;

```
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

```