Find the length of the loop

One of the popular interivew tasks…

You are given a head of a linked list. Its known list contains cycle. The goal is to determine the length of the loop.

Here is straghtforward solution in haskell

data Node a
instance Eq a => Eq (Node a)

next :: Node a -> Node a

data Phase = TryFindLoop | FindLength deriving (Eq)

loopSize :: Eq a => Node a -> Int
loopSize a = slowAndFast a a 0 TryFindLoop
  where slowAndFast :: (Eq node) =>
                       Node node -> Node node -> Int -> Phase -> Int
        slowAndFast slow fast len phase =
          let nextSlow = next slow
              nextPreFast = next fast
              nextFast = next nextPreFast in
          if (slow == nextPreFast || slow == nextFast) then
            if (phase == FindLength) then
              if (nextPreFast == nextFast) then 1
                2*(len+1) - len - (if slow == nextFast then 0 else 1)
            else slowAndFast nextSlow nextSlow 0 FindLength
            slowAndFast nextSlow nextFast (len + 1) phase

Complexity: time o(n), memory o(1)

The idea: consider two pointers ‘fast’ and ‘slow’. At each iteration ‘slow’ pointer makes one step, ‘fast’ - two steps. Somewhere ‘fast’ pointer touches ‘slow’ and you can find length of the loop.