tda - tipos de datos abstractos en java

¿Qué es un algoritmo eficiente para encontrar si una lista vinculada individualmente es circular/cíclica o no?

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cómo detectar un bucle en una lista vinculada? 23 respuestas

¿Cómo puedo saber si una lista vinculada individualmente es circular / cíclica o no? Traté de buscar pero no pude encontrar una solución satisfactoria. Si es posible, ¿puede proporcionar un pseudo-código o implementación de Java?

Por ejemplo:
1 → 3 → 5 → 71 → 45 → 7 → 5 , donde el segundo 5 es realmente el tercer elemento de la lista.

Answer 1

¿Qué hay de siguiente enfoque:

Ordene la lista de enlaces en orden ascendente siguiendo los algoritmos estándar. Antes de ordenar: 4-2-6-1-5 After Sort: 1-2-4-5-6

Una vez clasificados, verifique los datos de cada nodo y compárelos con los datos del nodo del enlace, algo como esto:

if (currentcode-> data> currentnode-> link-> data) es decir, circular = verdadero;

En cualquier comparación, si alguno de "currentnode-> data" es mayor que "currentcode-> link-> data" para una lista de enlaces ordenada, significa que el nodo actual apunta a un nodo anterior (es decir, circular);

Chicos, no tengo la configuración para probar el código. Déjenme ahora si este concepto funciona.

Answer 2

@samoz tiene en mi punto de vista la respuesta! Pseudo código faltante Sería algo así como

tu lista es tu lista enlazada

allnodes = hashmap
while yourlist.hasNext()
   node = yourlist.next()
   if(allnodes.contains(node))
      syso "loop found"
      break;
   hashmap.add(node)

lo siento, el código es muy pseudo (haga más scripting que java últimamente)

Answer 3

Aquí hay un buen sitio en el que se pueden copiar las diferentes soluciones.

encontrar la lista de enlaces individuales del bucle

Este es el ganador en ese sitio

// Best solution
function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Esta solución es el "Algoritmo de búsqueda de ciclos de Floyd" publicado en "Algoritmos no deterministas" por Robert W. Floyd en 1967. También se lo conoce como "Algoritmo de la liebre y la tortuga".

Answer 4

Comienza en un nodo y grábalo, luego recorre toda la lista hasta llegar a un puntero nulo o al nodo con el que comenzaste.

Algo como:

Node start = list->head;
Node temp = start->next;
bool circular = false;
while(temp != null && temp != start)
{
   if(temp == start)
   {
     circular = true;
     break;
   }
   temp = temp->next;
}
return circular

Esto es O (n), que es más o menos lo mejor que podrás obtener con una lista individualmente vinculada (corrígeme si estoy equivocado).

O para encontrar cualquier ciclo en la lista (como el medio), podría hacer:

Node[] array; // Use a vector or ArrayList to support dynamic insertions
Node temp = list->head;
bool circular = false;
while(temp != null)
{
   if(array.contains(temp) == true)
   {
     circular = true;
     break;
   }
   array.insert(temp);
   temp = temp->next;
}
return circular

Esto será un poco más lento debido a los tiempos de inserción de las matrices dinámicas.

Answer 5

Conté tus nodos y llego a * la cabeza otra vez.

Answer 6

La respuesta estándar es tomar dos iteradores al principio, incrementar el primero una vez y el segundo dos veces. Verifique si apuntan al mismo objeto. Luego, repita hasta que el que está aumentando dos veces llegue al primero o llegue al final.

Este algoritmo encuentra cualquier enlace circular en la lista, no solo que es un círculo completo.

Pseudo-código (no Java, no probado, fuera de mi cabeza)

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you''re done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
   }
}

Answer 7

Nunca terminará del bucle, también se puede hacer en la siguiente solución:

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you''re done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
      if(i.next()==j)
          break;
    }
}

Answer 8

Prueba esto

/* Link list Node */

struct Node {int data; struct Node * next; };

/ * Esta función devuelve verdadero si la lista enlazada es circular, de lo contrario es falsa. * / bool isCircular (struct Node * head) {// Una lista vacía de enlaces es circular if (head == NULL) return true;

// Next of head
struct Node *node = head->next;

// This loop would stope in both cases (1) If
// Circular (2) Not circular
while (node != NULL && node != head)
   node = node->next;

// If loop stopped because of circular
// condition
return (node == head);

}

Answer 9

Tres estrategias principales que conozco:

1. Comienza a recorrer la lista y realiza un seguimiento de todos los nodos que has visitado (por ejemplo, almacena sus direcciones en un mapa). Cada nuevo nodo que visite, verifique si ya lo ha visitado. Si ya ha visitado el nodo, obviamente hay un bucle. Si no hay un bucle, llegarás al final con el tiempo. Esto no es genial porque es O (N) la complejidad del espacio para almacenar la información adicional.

2. La solución Tortoise / Hare. Inicie dos punteros al principio de la lista. El primer puntero, la "tortuga" avanza un nodo en cada iteración. El otro puntero, la "liebre" avanza dos nodos en cada iteración. Si no hay ningún bucle, la liebre y la tortuga llegarán al final de la lista. Si hay un bucle, la liebre pasará la tortuga en algún momento y cuando eso suceda, sabrá que hay un bucle. Esta es O (1) complejidad espacial y un algoritmo bastante simple.

3. Usa el algoritmo para invertir una lista enlazada. Si la lista tiene un bucle, terminará al principio de la lista al intentar revertirla. Si no tiene un bucle, terminará de invertirlo y golpeará el final. Esta es O (1) complejidad espacial, pero un algoritmo ligeramente más feo.

Answer 10

Un algoritmo es:

1. Almacenar el puntero al primer nodo
2. Recorre la lista comparando cada puntero de nodo con este puntero
3. Si encuentra un puntero NULL, entonces su lista no está unida circularmente
4. Si se encuentra con el primer nodo mientras se cruza, entonces se trata de una lista con enlaces circulares

Answer 11

Un algoritmo simple llamado algoritmo de Floyd es tener dos punteros, a y b, que comienzan en el primer elemento de la lista vinculada. Luego, en cada paso, incrementa una vez yb dos veces. Repita hasta llegar al final de la lista (sin bucle), o a == b (la lista vinculada contiene un bucle).

Otro algoritmo es el algoritmo de Brent .

Answer 12

Use el algoritmo Tortoise-Hare .