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;
    }
}

```
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]);
    }
}

```