Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

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());
  }
}
share|improve this question
2  
It is possible solve it with O(1) memory consumption. – CheatEx May 30 '11 at 18:01

4 Answers

up vote 5 down vote accepted 
  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.

share|improve this answer
You never check for the end of the list, so a non-loopy list will throw a NullPointerException. I believe the for should be for(Node node = head; node != null; node = node.next) – raptortech97 Apr 22 at 21:43
@raptortech97, thanks. It looks like I slipped in to a C++ism. – Winston Ewert♦ Apr 22 at 22:19
up vote 6 down vote

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.

share|improve this answer
You might want to explain how that algorithm works, and how it's better than the OP's suggested solution. – Tim Martin May 31 '11 at 17:43
@Tim Martin - Okay, done. – Rex Kerr May 31 '11 at 17:46
up vote 0 down vote 
Node n = null;

In Java, objects by default initialized to null, so

Node n;
share|improve this answer
2  
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. – RoToRa May 31 '11 at 12:03
up vote 0 down vote

To check that a list has a loop in its internals is only useful when testing the list implementation itself (I don't see how the standard List interface would make it possible to create a loop from client code), therefore I would care little about the efficiency of the test code, and would not have any extra fields or extra classes in the implementation itself; extra fields to track the visit would cost memory at every use of the structure, and extra code would increase the amount of bytecode that needs to be loaded. That would slow down class loading, by a small amount but this might add up. I believe KISS suggests this code to go in a nice test case that doesn't follow the list around.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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