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;

```
D
=

This is a solution I thought of myself. It runs in O(n) and uses O(1) memory.

What I'm doing is simply iterating through the list and reversing all the pointers. If the list contains a cycle, you'll eventually end up at the beginning of the list and otherwise you end up at the end, which is somewhere else if your list is longer than 1. Now you've determined the result you can restore the list by simply reversing the pointers again.

Here is my code and a test:

```
import std.stdio;

// The list structure.
struct node(T)
{
    T data;
    node!T * next;

    this(T data) {this.data = data; next = null;}
}

bool hasLoop(T)(node!T * first)
{
    // List shorter than two nodes has no loops.
    if(!first || !first.next)
    {
        return false;
    }

    // Keep iterating through the list, while reversing the pointers.
    node!T * previous = null, 
             current = first;
    while(current)
    {
        auto next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    // If the last node was the beginning of the list, there was a cycle.
    // Otherwise, there are none.
    bool result = previous == first;

    // Do the reversal again to restore the list to its original state.
    current = previous;
    previous = null;
    while(current)
    {
        auto next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    // Done!
    return result;
}

// Test
unittest
{
    // Build a list.
    int[] elems = [1,2,3,4,5,6,7,8,42];

    auto list = new node!int(elems[0]);
    auto curr = list;
    foreach(x; elems[1..$])
    {
        curr.next = new node!int(x);
        curr = curr.next;
    }

    // Outcomment the line below to test for a non-cycle list.
    curr.next = list.next.next.next;

    // Do cycle check.
    writeln(hasLoop(list) ? "yes" : "no");

    // Confirm the list is still correct.
    curr = list;
    for(int i = 0; i < elems.length; ++i, curr = curr.next)
    {
        assert(curr.data == elems[i]);
    }
}

```