linkedlist entre diferencia definicion linked-list

linked list - entre - Encontrando bucle en una lista enlazada individualmente



linkedlist java definicion (10)

¿Cómo puedo detectar si una lista enlazada individualmente tiene un bucle o no? Si tiene un bucle, entonces cómo encontrar el punto de origen del bucle, es decir, el nodo desde el cual se inició el bucle.

El siguiente código encontrará si hay un bucle en SLL y, si existe, regresará al nodo inicial.

int find_loop(Node *head){ Node * slow = head; Node * fast = head; Node * ptr1; Node * ptr2; int k =1, loop_found =0, i; if(!head) return -1; while(slow && fast && fast->next){ slow = slow->next; /*Moving fast pointer two steps at a time */ fast = fast->next->next; if(slow == fast){ loop_found = 1; break; } } if(loop_found){ /* We have detected a loop */ /*Let''s count the number of nodes in this loop node */ ptr1 = fast; while(ptr1 && ptr1->next != slow){ ptr1 = ptr1->next; k++; } /* Now move the other pointer by K nodes */ ptr2 = head; ptr1 = head; for(i=0; i<k; i++){ ptr2 = ptr2->next; } /* Now if we move ptr1 and ptr2 with same speed they will meet at start of loop */ while(ptr1 != ptr2){ ptr1 = ptr1->next; ptr2 = ptr2->next; } return ptr1->data; }

La respuesta seleccionada proporciona una solución O (n * n) para encontrar el nodo de inicio del ciclo. Aquí hay una solución O (n):

Una vez que encontremos la reunión lenta A y rápida B en el ciclo, haga que una de ellas se detenga y la otra continúe dando un paso cada vez, para decidir el perímetro del ciclo, por ejemplo, P.

Luego ponemos un nodo en la cabeza y lo dejamos ir P pasos, y ponemos otro nodo en la cabeza. Avanzamos estos dos nodos un paso cada vez, cuando se encuentran por primera vez, es el punto de inicio del ciclo.

Leí esta respuesta en el libro Estructura de datos de Narasimha Karamanchi.

Podemos usar el algoritmo de búsqueda de ciclos de Floyd , también conocido como algoritmo de tortuga y liebre . En esto, se utilizan dos punteros; uno (por ejemplo, slowPtr ) es avanzado por un solo nodo, y otro (por ejemplo, fastPtr ) es avanzado por dos nodos. Si algún bucle está presente en la lista enlazada única, ambos seguramente se encontrarán en algún momento.

struct Node{ int data; struct Node *next; } // program to find the begin of the loop int detectLoopandFindBegin(struct Node *head){ struct Node *slowPtr = head, *fastPtr = head; int loopExists = 0; // this while loop will find if there exists a loop or not. while(slowPtr && fastPtr && fastPtr->next){ slowPtr = slowPtr->next; fastPtr = fastPtr->next->next; if(slowPtr == fastPtr) loopExists = 1; break; }

Si existe algún bucle, entonces apuntamos uno de los punteros a la cabeza y ahora avanzamos ambos por un solo nodo. El nodo en el que se encontrarán será el nodo de inicio del bucle en la lista enlazada única.

if(loopExists){ slowPtr = head; while(slowPtr != fastPtr){ fastPtr = fastPtr->next; slowPtr = slowPtr->next; } return slowPtr; } return NULL; }

Mientras veía la respuesta seleccionada, probé un par de ejemplos y encontré que:
Si (A1, B1), (A2, B2) ... (AN, BN) son los recorridos de los punteros A y B
donde A pasos 1 elemento y B pasos 2 elementos, y, Ai y Bj son los nodos atravesados ​​por A y B, y AN = BN.
Entonces, el nodo desde donde comienza el bucle es Ak, donde k = piso (N / 2).

Otra solución

Detectando un Loop:

  1. Crear una lista
  2. recorre la lista enlazada y continúa agregando el nodo a la lista.
  3. Si el Nodo ya está presente en la Lista, tenemos un bucle.

Eliminación de bucle:

  1. En el Paso # 2 anterior, mientras recorre la lista enlazada, también hacemos un seguimiento del nodo anterior.

  2. Una vez que detectamos el bucle en el Paso 3, establezca el siguiente valor del nodo anterior en NULL

    #código

    def detect_remove_loop (head)

    cur_node = head node_list = [] while cur_node.next is not None: prev_node = cur_node cur_node = cur_node.next if cur_node not in node_list: node_list.append(cur_node) else: print(''Loop Detected'') prev_node.next = None return print(''No Loop detected'')

Puede detectarlo simplemente ejecutando dos punteros a través de la lista, este proceso se conoce como algoritmo de tortuga y liebre después de la fábula del mismo nombre.

En primer lugar, compruebe si la lista está vacía (el head es null ). Si es así, ningún bucle es posible, así que pare ahora.

De lo contrario, inicie la primera tortoise puntero en el primer nodo y la segunda hare puntero en el segundo nodo head.next .

Luego haga un bucle continuo hasta que la hare sea null (lo que ya puede ser cierto en una lista de un elemento), avanzando tortoise por una y hare por dos en cada iteración. Se garantiza que la liebre llegará al final primero (si hay un final) ya que comenzó adelante y corre más rápido.

Si no hay un final (es decir, si hay un bucle), eventualmente apuntarán al mismo nodo y usted puede detenerse, sabiendo que ha encontrado un nodo en algún lugar dentro del bucle.

Considere el siguiente bucle que comienza en 3 :

head -> 1 -> 2 -> 3 -> 4 -> 5 ^ | | V 8 <- 7 <- 6

La tortoise partida en 1 y la hare en 2, toman los siguientes valores:

(tortoise,hare) = (1,2) (2,4) (3,6) (4,8) (5,4) (6,6)

Debido a que se vuelven iguales en (6,6) , y dado que la hare siempre debe estar más allá de la tortoise en una lista sin bucle, significa que ha descubierto un bucle.

El pseudo-código irá algo así:

def hasLoop (head): return false if head = null # Empty list has no loop. tortoise = head # tortoise initially first element. hare = tortoise.next # Set hare to second element. while hare != null: # Go until hare reaches end. return false if hare.next null # Check enough left for hare move. hare = hare.next.next # Move hare forward two. tortoise = tortoise.next # Move tortoise forward one. return true if hare = tortoise # Same means loop found. endwhile return false # Loop exit means no loop. enddef

La complejidad del tiempo para este algoritmo es O(n) ya que el número de nodos visitados (por tortuga y liebre) es proporcional al número de nodos.

Una vez que conoce un nodo dentro del bucle, también hay un método O(n) garantizado para encontrar el inicio del bucle.

Regresemos a la posición original después de haber encontrado un elemento en algún lugar del bucle, pero no está seguro de dónde está el inicio del bucle.

head -> 1 -> 2 -> 3 -> 4 -> 5 ^ | | V 8 <- 7 <- 6 / x (where hare and tortoise met).

Este es el proceso a seguir:

  • Avanza la hare y establece el size en 1 .
  • Luego, siempre que la hare y la tortoise sean diferentes, continúe avanzando, aumentando el size cada vez. Esto eventualmente da el tamaño del bucle, seis en este caso.
  • En este punto, si el size es 1 , eso significa you must *already* be at the start of the loop (in a loop of size one, there is only one possible node that can *be* in the loop so it *must* be the first in that loop). In this case, you simply return you must *already* be at the start of the loop (in a loop of size one, there is only one possible node that can *be* in the loop so it *must* be the first in that loop). In this case, you simply return hare` como inicio y omita el resto de los pasos a continuación.
  • De lo contrario, establezca tanto la hare como la tortoise en el primer elemento de la lista y hare avanzar el size exacto de la hare (hasta el 7 en este caso). Esto da dos punteros que son diferentes por el tamaño exacto del bucle.
  • Luego, siempre que la hare y la tortoise sean diferentes, hágalos avanzar juntos (con la liebre corriendo a un ritmo más tranquilo, a la misma velocidad que la tortuga, supongo que está cansada desde su primera ejecución). Dado que permanecerán exactamente elementos de size separados entre sí en todo momento, tortoise alcanzará el inicio del bucle exactamente al mismo tiempo que la hare regresa al comienzo del bucle.

Puedes ver eso con el siguiente tutorial:

size tortoise hare comment ---- -------- ---- ------- 6 1 1 initial state 7 advance hare by six 2 8 1/7 different, so advance both together 3 3 2/8 different, so advance both together 3/3 same, so exit loop

Por lo tanto, 3 es el punto de inicio del bucle y, dado que ambas operaciones (la detección de bucle y el descubrimiento de inicio de bucle) son O(n) y se realizan de forma secuencial, todo lo que se toma en conjunto también es O(n) .

Si desea una prueba más formal de que esto funciona, puede examinar los siguientes recursos:

Si simplemente está buscando soporte para el método (no es una prueba formal), puede ejecutar el siguiente programa Python 3 que evalúa su capacidad de trabajo para una gran cantidad de tamaños (cuántos elementos en el ciclo) y entradas (elementos antes de la inicio del ciclo).

Encontrarás que siempre encuentra un punto donde los dos punteros se encuentran:

def nextp(p, ld, sz): if p == ld + sz: return ld return p + 1 for size in range(1,1001): for lead in range(1001): p1 = 0 p2 = 0 while True: p1 = nextp(p1, lead, size) p2 = nextp(nextp(p2, lead, size), lead, size) if p1 == p2: print("sz = %d, ld = %d, found = %d" % (size, lead, p1)) break

También puede utilizar el mapa hash para determinar si una lista de enlaces tiene un bucle o no. La función inferior utiliza el mapa hash para averiguar si la lista de enlaces tiene un bucle

static bool isListHaveALoopUsingHashMap(Link *headLink) { map<Link*, int> tempMap; Link * temp; temp = headLink; while (temp->next != NULL) { if (tempMap.find(temp) == tempMap.end()) { tempMap[temp] = 1; } else { return 0; } temp = temp->next; } return 1; }

El método de dos punteros es el mejor enfoque porque la complejidad del tiempo es O (n) El mapa hash requiere la complejidad del espacio O (n) adicional.

Un método bastante diferente: - Invertir la lista enlazada. Mientras retrocede, si alcanza la cabeza nuevamente, habrá un bucle en la lista; si obtiene NULL, no habrá ningún bucle. La complejidad del tiempo total es O (n)

ok, me encontré con esto en una entrevista ayer: no hay material de referencia disponible y se me ocurrió una respuesta muy diferente (mientras conducía a casa, por supuesto ...) Dado que las listas enlazadas están NORMALMENTE (no siempre lo admito) asignadas usando la lógica malloc entonces sabemos que la granularidad de las asignaciones es conocida. En la mayoría de los sistemas, esto es de 8 bytes, lo que significa que los 3 bits inferiores siempre son ceros. Considere: si colocamos la lista enlazada en una clase para controlar el acceso y usamos una máscara de 0x0E ored en la siguiente dirección, entonces podemos usar los 3 bits inferiores para almacenar una migaja de ruptura. Así, podemos escribir un método que almacenará nuestra última ruta de navegación. - Di 1 o 2 - y alternalas. Nuestro método que comprueba si hay un bucle puede pasar a través de cada nodo (utilizando nuestro siguiente método) y verificar si la siguiente dirección contiene la ruta de navegación actual. Si tiene un bucle, si no lo hace, enmascararemos los 3 bits más bajos. y añadir nuestra migaja de pan actual. El algoritmo de comprobación de ruta de navegación tendría que ser de un solo hilo, ya que no podría ejecutar dos de ellos a la vez, pero permitiría que otros subprocesos accedieran a la lista de forma asíncrona, con las advertencias habituales sobre la adición / eliminación de nodos. ¿Qué piensas? Si otros piensan que esta es una solución válida, puedo escribir la clase de muestra ... Pienso que a veces un nuevo enfoque es bueno y siempre estoy dispuesto a que me digan que acabo de perder el punto ... Gracias a todos.

boolean hasLoop(Node *head) { Node *current = head; Node *check = null; int firstPtr = 0; int secondPtr = 2; do { if (check == current) return true; if (firstPtr >= secondPtr){ check = current; firstPtr = 0; secondPtr= 2*secondPtr; } firstPtr ++; } while (current = current->next()); return false; }

Otra solución O (n).