current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 7 down vote favorite

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

3 Answers 3

up vote 8 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
up vote 0 down vote 
Node n = null;

In Java, objects by default initialized to null, so

Node n;
share|improve this answer
3  
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 8 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
1  
More information about the algorithm can be found in the wiki page for Tortoise and Hare algorithm: en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare –  pgreen2 Jul 22 '14 at 13:11

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.