java - objetos - ¿Cómo detectar un bucle en una lista enlazada?
generar varios objetos java (23)
Aquí está la solución para detectar el ciclo.
public boolean hasCycle(ListNode head) {
ListNode slow =head;
ListNode fast =head;
while(fast!=null && fast.next!=null){
slow = slow.next; // slow pointer only one hop
fast = fast.next.next; // fast pointer two hops
if(slow == fast) return true; // retrun true if fast meet slow pointer
}
return false; // return false if fast pointer stop at end
}
Digamos que tienes una estructura de lista vinculada en Java. Se compone de nodos:
class Node {
Node next;
// some user data
}
y cada nodo apunta al siguiente nodo, excepto el último nodo, que tiene nulo para el siguiente. Supongamos que existe la posibilidad de que la lista pueda contener un bucle; es decir, el nodo final, en lugar de tener un nulo, tiene una referencia a uno de los nodos de la lista que venía antes.
¿Cuál es la mejor forma de escribir?
boolean hasLoop(Node first)
¿cuál devolvería true si el nodo dado es el primero de una lista con un bucle, y false contrario? ¿Cómo podrías escribir para que tome una cantidad constante de espacio y una cantidad de tiempo razonable?
Aquí hay una imagen de cómo se ve una lista con un bucle:
Aquí está mi código ejecutable.
Lo que he hecho es reverberar la lista vinculada mediante el uso de tres nodos temporales (complejidad de espacio O(1) ) que realizan un seguimiento de los enlaces.
El hecho interesante de hacerlo es ayudar a detectar el ciclo en la lista enlazada porque a medida que avanza, no espera volver al punto de inicio (nodo raíz) y uno de los nodos temporales debe ir a nulo a menos que tiene un ciclo que significa que apunta al nodo raíz.
La complejidad temporal de este algoritmo es O(n) y la complejidad del espacio es O(1) .
Aquí está el nodo de clase para la lista enlazada:
public class LinkedNode{
public LinkedNode next;
}
Aquí está el código principal con un caso de prueba simple de tres nodos que el último nodo apunta al segundo nodo:
public static boolean checkLoopInLinkedList(LinkedNode root){
if (root == null || root.next == null) return false;
LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
root.next = null;
current2.next = current1;
while(current3 != null){
if(current3 == root) return true;
current1 = current2;
current2 = current3;
current3 = current3.next;
current2.next = current1;
}
return false;
}
Este es un caso de prueba simple de tres nodos que el último nodo apunta al segundo nodo:
public class questions{
public static void main(String [] args){
LinkedNode n1 = new LinkedNode();
LinkedNode n2 = new LinkedNode();
LinkedNode n3 = new LinkedNode();
n1.next = n2;
n2.next = n3;
n3.next = n2;
System.out.print(checkLoopInLinkedList(n1));
}
}
Aquí está mi solución en java
boolean detectLoop(Node head){
Node fastRunner = head;
Node slowRunner = head;
while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
fastRunner = fastRunner.next.next;
slowRunner = slowRunner.next;
if(fastRunner == slowRunner){
return true;
}
}
return false;
}
Aquí hay un refinamiento de la solución Rápida / Lenta, que maneja correctamente las listas de longitudes impares y mejora la claridad.
boolean hasLoop(Node first) {
Node slow = first;
Node fast = first;
while(fast != null && fast.next != null) {
slow = slow.next; // 1 hop
fast = fast.next.next; // 2 hops
if(slow == fast) // fast caught up to slow, so there is a loop
return true;
}
return false; // fast reached null, so the list terminates
}
El siguiente método puede no ser el mejor, es O (n ^ 2). Sin embargo, debería servir para hacer el trabajo (eventualmente).
count_of_elements_so_far = 0;
for (each element in linked list)
{
search for current element in first <count_of_elements_so_far>
if found, then you have a loop
else,count_of_elements_so_far++;
}
El usuario unicornaddict tiene un buen algoritmo arriba, pero desafortunadamente contiene un error para las listas de longitud impar> = 3. El problema es que fast puede "atascar" justo antes del final de la lista. , y se detecta (erróneamente) un bucle.
Aquí está el algoritmo corregido.
static boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either.
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list.
while(true) {
slow = slow.next; // 1 hop.
if(fast.next == null)
fast = null;
else
fast = fast.next.next; // 2 hops.
if(fast == null) // if fast hits null..no loop.
return false;
if(slow == fast) // if the two ever meet...we must have a loop.
return true;
}
}
Este código está optimizado y producirá un resultado más rápido que con el elegido como la mejor respuesta. Este código evita pasar por un proceso muy largo de perseguir el puntero del nodo hacia adelante y hacia atrás, lo que ocurrirá en el siguiente caso si seguimos el "mejor" Método de respuesta. Mire detenidamente lo siguiente y se dará cuenta de lo que estoy tratando de decir. Luego mire el problema a través del método dado a continuación y mida el no. de pasos tomados para encontrar la respuesta.
1-> 2-> 9-> 3 ^ -------- ^
Aquí está el código:
boolean loop(node *head)
{
node *back=head;
node *front=head;
while(front && front->next)
{
front=front->next->next;
if(back==front)
return true;
else
back=back->next;
}
return false
}
Este enfoque tiene una sobrecarga de espacio, pero una implementación más simple:
El bucle se puede identificar almacenando nodos en un mapa. Y antes de poner el nodo; Compruebe si el nodo ya existe. Si el nodo ya existe en el mapa, significa que la Lista vinculada tiene un bucle.
public boolean loopDetector(Node<E> first) {
Node<E> t = first;
Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();
while (t != null) {
if (map.containsKey(t)) {
System.out.println(" duplicate Node is --" + t
+ " having value :" + t.data);
return true;
} else {
map.put(t, t);
}
t = t.next;
}
return false;
}
Incluso podría hacerlo en tiempo O constante (aunque no sería muy rápido ni eficiente): hay una cantidad limitada de nodos que la memoria de su computadora puede contener, digamos N registros. Si recorres más de N registros, entonces tienes un bucle.
La detección de un bucle en una lista enlazada se puede hacer de una de las formas más simples, lo que resulta en una complejidad O (N).
A medida que recorre la lista comenzando desde la cabeza, cree una lista ordenada de direcciones. Cuando inserte una nueva dirección, verifique si la dirección ya está allí en la lista ordenada, lo que toma complejidad O (logN).
No veo ninguna manera de hacer que esto tome una cantidad fija de tiempo o espacio, ambos aumentarán con el tamaño de la lista.
Haría uso de un IdentityHashMap (dado que todavía no hay un IdentityHashSet) y almacenaría cada nodo en el mapa. Antes de que se almacene un nodo, debe llamar a contieneKey en él. Si el nodo ya existe tienes un ciclo.
ItentityHashMap usa == en lugar de .equals para que compruebe dónde está el objeto en la memoria en lugar de si tiene el mismo contenido.
Podría ser terriblemente tarde y nuevo para manejar este hilo. Pero aún..
¿Por qué no se puede almacenar la dirección del nodo y el nodo "siguiente" señalado en una tabla?
Si pudiéramos tabular de esta manera.
node present: (present node addr) (next node address)
node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)
De ahí que se forme un ciclo.
Puede hacer uso del algoritmo de búsqueda de ciclos de Floyd , también conocido como algoritmo de tortuga y liebre .
La idea es tener dos referencias a la lista y moverlas a diferentes velocidades . Mueve uno hacia adelante por 1 nodo y el otro por 2 nodos.
- Si la lista enlazada tiene un bucle definitivamente se reunirán.
- De lo contrario, cualquiera de las dos referencias (o las
next) se volveránnull.
Función de Java implementando el algoritmo:
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list
while(true) {
slow = slow.next; // 1 hop
if(fast.next != null)
fast = fast.next.next; // 2 hops
else
return false; // next node null => no loop
if(slow == null || fast == null) // if either hits null..no loop
return false;
if(slow == fast) // if the two ever meet...we must have a loop
return true;
}
}
Si se nos permite incrustar la clase Node , resolvería el problema tal como lo he implementado a continuación. hasLoop() ejecuta en tiempo O (n) y solo ocupa el espacio del counter . ¿Parece esto una solución adecuada? ¿O hay una manera de hacerlo sin incrustar Node ? (Obviamente, en una implementación real habría más métodos, como RemoveNode(Node n) , etc.)
public class LinkedNodeList {
Node first;
Int count;
LinkedNodeList(){
first = null;
count = 0;
}
LinkedNodeList(Node n){
if (n.next != null){
throw new error("must start with single node!");
} else {
first = n;
count = 1;
}
}
public void addNode(Node n){
Node lookingAt = first;
while(lookingAt.next != null){
lookingAt = lookingAt.next;
}
lookingAt.next = n;
count++;
}
public boolean hasLoop(){
int counter = 0;
Node lookingAt = first;
while(lookingAt.next != null){
counter++;
if (count < counter){
return false;
} else {
lookingAt = lookingAt.next;
}
}
return true;
}
private class Node{
Node next;
....
}
}
También puede usar el algoritmo de tortuga de Floyd como se sugiere en las respuestas anteriores.
Este algoritmo puede verificar si una lista enlazada individualmente tiene un ciclo cerrado. Esto se puede lograr mediante la iteración de una lista con dos punteros que se moverán a una velocidad diferente. De esta manera, si hay un ciclo, los dos punteros se encontrarán en algún momento en el futuro.
No dude en consultar mi blog en la estructura de datos de listas vinculadas, donde también incluí un fragmento de código con una implementación del algoritmo mencionado anteriormente en lenguaje java.
Saludos,
Andreas (@xnorcode)
Una solución alternativa a la tortuga y al conejo, no tan agradable, ya que cambio temporalmente la lista:
La idea es recorrer la lista y revertirla a medida que avanza. Luego, cuando llega por primera vez a un nodo que ya ha sido visitado, su siguiente puntero apuntará "hacia atrás", lo que provocará que la iteración continúe hacia el first , donde termina.
Node prev = null;
Node cur = first;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;
// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return hasCycle;
Código de prueba:
static void assertSameOrder(Node[] nodes) {
for (int i = 0; i < nodes.length - 1; i++) {
assert nodes[i].next == nodes[i + 1];
}
}
public static void main(String[] args) {
Node[] nodes = new Node[100];
for (int i = 0; i < nodes.length; i++) {
nodes[i] = new Node();
}
for (int i = 0; i < nodes.length - 1; i++) {
nodes[i].next = nodes[i + 1];
}
Node first = nodes[0];
Node max = nodes[nodes.length - 1];
max.next = null;
assert !hasCycle(first);
assertSameOrder(nodes);
max.next = first;
assert hasCycle(first);
assertSameOrder(nodes);
max.next = max;
assert hasCycle(first);
assertSameOrder(nodes);
max.next = nodes[50];
assert hasCycle(first);
assertSameOrder(nodes);
}
Eche un vistazo al algoritmo rho de Pollard . No es exactamente el mismo problema, pero tal vez comprenda la lógica y lo aplique a las listas vinculadas.
(Si es perezoso, solo puede verificar la detección de ciclos , verifique la parte sobre la tortuga y la liebre).
Esto solo requiere tiempo lineal, y 2 punteros extra.
En Java:
boolean hasLoop( Node first ) {
if ( first == null ) return false;
Node turtle = first;
Node hare = first;
while ( hare.next != null && hare.next.next != null ) {
turtle = turtle.next;
hare = hare.next.next;
if ( turtle == hare ) return true;
}
return false;
}
(La mayoría de las soluciones no comprueban el next ni el next next.next busca de next.next nulos. Además, dado que la tortuga siempre está detrás, no es necesario que verifique que no haya ningún problema, ya que la liebre ya lo hizo).
Mejor que el algoritmo de Floyd
Richard Brent describió un algoritmo de detección de ciclo alternativo , que es muy parecido a la liebre y la tortuga [ciclo de Floyd], excepto que el nodo lento aquí no se mueve, sino que más tarde se "teletransporta" a la posición del nodo rápido en posición fija. intervalos
La descripción está disponible aquí: http://www.siafoo.net/algorithm/11 Brent afirma que su algoritmo es 24 a 36% más rápido que el algoritmo de ciclo de Floyd. O (n) complejidad de tiempo, O (1) complejidad de espacio.
public static boolean hasLoop(Node root){
if(root == null) return false;
Node slow = root, fast = root;
int taken = 0, limit = 2;
while (fast.next != null) {
fast = fast.next;
taken++;
if(slow == fast) return true;
if(taken == limit){
taken = 0;
limit <<= 1; // equivalent to limit *= 2;
slow = fast; // teleporting the turtle (to the hare''s position)
}
}
return false;
}
Algoritmo
public static boolean hasCycle (LinkedList<Node> list)
{
HashSet<Node> visited = new HashSet<Node>();
for (Node n : list)
{
visited.add(n);
if (visited.contains(n.next))
{
return true;
}
}
return false;
}
Complejidad
Time ~ O(n)
Space ~ O(n)
// To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
Node slower, faster;
slower = head;
faster = head.next; // start faster one node ahead
while (true) {
// if the faster pointer encounters a NULL element
if (faster == null || faster.next == null)
return false;
// if faster pointer ever equals slower or faster''s next
// pointer is ever equal to slower then it''s a circular list
else if (slower == faster || slower == faster.next)
return true;
else {
// advance the pointers
slower = slower.next;
faster = faster.next.next;
}
}
}
boolean hasCycle(Node head) {
boolean dec = false;
Node first = head;
Node sec = head;
while(first != null && sec != null)
{
first = first.next;
sec = sec.next.next;
if(first == sec )
{
dec = true;
break;
}
}
return dec;
}
Utilice la función anterior para detectar un bucle en la lista enlazada en java.
public boolean hasLoop(Node start){
TreeSet<Node> set = new TreeSet<Node>();
Node lookingAt = start;
while (lookingAt.peek() != null){
lookingAt = lookingAt.next;
if (set.contains(lookingAt){
return false;
} else {
set.put(lookingAt);
}
return true;
}
// Inside our Node class:
public Node peek(){
return this.next;
}
Perdóname mi ignorancia (todavía soy bastante nuevo en Java y programación), pero ¿por qué no funcionaría lo anterior?
Supongo que esto no resuelve el problema del espacio constante ... pero al menos llega en un tiempo razonable, ¿correcto? Solo tomará el espacio de la lista enlazada más el espacio de un conjunto con n elementos (donde n es el número de elementos en la lista enlazada, o el número de elementos hasta que alcance un bucle). Y por el momento, creo que el análisis del peor de los casos sugeriría O (nlog (n)). Las búsquedas de SortedSet para contiene () son log (n) (verifique el javadoc, pero estoy bastante seguro de que la estructura subyacente de TreeSet es TreeMap, que a su vez es un árbol rojo-negro), y en el peor de los casos (sin bucles, o bucle al final), tendrá que hacer n búsquedas.
public boolean isCircular() {
if (head == null)
return false;
Node temp1 = head;
Node temp2 = head;
try {
while (temp2.next != null) {
temp2 = temp2.next.next.next;
temp1 = temp1.next;
if (temp1 == temp2 || temp1 == temp2.next)
return true;
}
} catch (NullPointerException ex) {
return false;
}
return false;
}