Linked list loop detection in Java A schoolmate is going through the interview process, and was given the question of detecting if a linked list data structure has an infinite loop in it. I wrote this example, and wanted to see what experience programmers thought of it.

/*
* detecting loops in a linked list, java
*
* This linked list doesn't have a payload, but that is irrelevant to
* this problem, although might be useful for debugging.
*
*/

import java.util.*;

class Node
{
  Node n = null;
  Node()
  {
  }
  Node(Node n)
  {
    setNext(n);
  }
  void setNext(Node n)
  {
    this.n = n;
  }
  boolean hasNext()
  {
    return n!=null;
  }
  Node next()
  {
    return n;
  }
  boolean isLoopy(Set&lt;Node&gt; visited)
  {
    if(visited.contains(this))
    {
      return true;
    }else
    {
      if(hasNext())
      {
        visited.add(this);
        return next().isLoopy(visited);
      }else
      {
        return false;
      }
    }
  }
  boolean isLoopy()
  {
    return isLoopy(new HashSet&lt;Node&gt;());
  }
  // test harness
  public static void main(String[] args)
  {
    Node n1 = new Node();
    Node n2 = new Node(n1);
    n1.setNext(n2);

    System.out.println("loopy list is loopy:");
    System.out.println(n1.isLoopy());

    Node n4 = new Node();
    Node n3 = new Node(n4);

    System.out.println("non loopy list is loopy:");
    System.out.println(n3.isLoopy());
  }
}
This is a classic interview question.  At this point, I think it measures more whether you've been to many interviews than whether you can think creatively algorithmically while on a job interview.  Anyway,

public class Node {
  public Node next = null;
  public Node() {}
  public Node(Node n) { next = n; }
  public boolean hasNext() { return next != null; }
  public boolean hasLoop() {
    Node n = this, n2 = this;
    while (n.hasNext()) {
      n = n.next;
      if (n == n2) return true;
      if (!n.hasNext()) return false;
      n = n.next;
      if (n == n2) return true;
      n2 = n2.next;
    }
    return false;
  }
}


(Not compiled, but you get the idea.  I think getters/setters for next is overkill, given that the whole point is to manipulate the field at a low level, given this data structure.)

This uses constant space; since n travels twice as fast as n2, if there is a loop, both n and n2 will get caught at it and n will overtake n2 from behind (after a maximum number of steps equal to twice (lead-in plus loop length)).  Otherwise, n will reach the end and we're done.