Связанный список обнаружения цикла в Java


Одноклассница собирается через процесс интервью, и был дан на вопрос, обнаруживая связанный список структура данных имеет бесконечный цикл в нем. Я написал этот пример, и хотел посмотреть, что программисты думал об этом.

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


2900
10
задан 30 мая 2011 в 03:05 Источник Поделиться
Комментарии
3 ответа

  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);

На первый взгляд, кажется странным, что эта линия не вне if-блок. Я вижу, что это не имеет значения. Однако, по крайней мере, комментарий, объясняющий, почему вы разместили его здесь.

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

Ваш код является рекурсивным, но это не нужно. Было бы лучше, как метод класса List (или статический метод узла):

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;
}

Я думаю, что этот код чище и более эффективным.

10
ответ дан 30 мая 2011 в 03:05 Источник Поделиться

Это классический вопрос. На данный момент, я думаю, что это больше мер, будь вы были на многих интервью, чем можно ли творчески мыслить алгоритмически, а на собеседование. В любом случае,

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;
}
}

(Не компилируется, но вы получаете идею. Я думаю, что геттеры/сеттеры на следующий уже перебор, учитывая, что весь смысл в том, чтобы манипулировать области на низком уровне, учитывая структуру данных.)

При этом используется постоянное пространство; с н едет вдвое быстрее, чем Н2, если есть петля, как Н и Н2 поймают его и Н обгонит Н2 сзади (после максимальное число шагов равно в два раза (свинец-в плюс петля длина)). В противном случае, н дойдет до конца и мы закончили.

12
ответ дан 31 мая 2011 в 03:05 Источник Поделиться

Node n = null;

В Java, объекты по умолчанию инициализируются в null, так

Node n;

-1
ответ дан 30 мая 2011 в 08:05 Источник Поделиться