10
\$\begingroup\$

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());
  }
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ It is possible solve it with O(1) memory consumption. \$\endgroup\$
    – CheatEx
    May 30, 2011 at 18:01

3 Answers 3

10
\$\begingroup\$
  void setNext(Node n)
  {
    this.n = n;
  }
  boolean hasNext()
  {
    return n!=null;
  }
  Node next()
  {
    return n;
  }

I think the getters and setters are misplaced here. Such methods should be used to hide the internal details of an implementation. However, the entire Node class is the internal details of a List class. As such having getters and setters just complicates the situation.

  boolean isLoopy(Set<Node> visited)

An option to consider is storing a visited flag on the nodes rather then as a set.

  {
    if(visited.contains(this))
    {
      return true;
    }else
    {

That's a new way of arranging else that I haven't seen before.

      if(hasNext())
      {
        visited.add(this);

At first glance, it seems odd that this line isn't outside of the if-block. I can see that it doesn't matter. However, at least a comment explaining why you've put it here.

        return next().isLoopy(visited);
      }else
      {
        return false;
      }
    }
  }

Your code is recursive but it doesn't need to be. It would better as a method on a list class (or a static Node method):

boolean isLoopy()
{
    Set<Node> visited = new HashSet<Node>();
    for(Node node = head; node != null; node = node.next)
    {
         if( visited.contains(node) )
         {
             return true;
         }else{
             visited.add(node);
         }
     }
     return false;
}

I think this code is clearer and somewhat more efficient.

\$\endgroup\$
0
12
\$\begingroup\$

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.

\$\endgroup\$
1
-1
\$\begingroup\$
Node n = null;

In Java, objects by default initialized to null, so

Node n;
\$\endgroup\$
1
  • 4
    \$\begingroup\$ Setting a variable on declaration explicitly to null is a good thing to do, because it indicates to a reader of the code, that this variable purposely may not be assigned to. \$\endgroup\$
    – RoToRa
    May 31, 2011 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.