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

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

```