A schoolmate is going through the interview process, and was posed 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 though 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<Node> 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<Node>());
  }
  // 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());
  }
}

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<Node> 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<Node>());
  }
  // 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());
  }
}