detectar el inicio de un bucle en una lista de enlaces de enlace simple?
https://stackoverflow.com/questions/1536944
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Hay alguna forma de averiguar el inicio de un bucle en una lista de enlaces usando no más de dos punteros? No quiero visitar cada nodo y marcarlo visto e informar el primer nodo ya ha habido seen.Is Hay alguna otra manera de hacer esto?
Solución
He escuchado esta pregunta exacta como una pregunta de la entrevista prueba.
La solución más elegante es:
Ponga ambos punteros en el primer elemento (que llamaremos A y B)
A continuación, seguirá sonando ::
- Advance A al siguiente elemento
- Advance A al siguiente elemento de nuevo
- Advance B al siguiente elemento
Si desea realmente encontrar el elemento que tiene dos punteros que apuntan a la misma, que es más difícil. Me gustaría salir de una extremidad y decir que es imposible de hacer con sólo dos punteros a menos que esté dispuesto a repetir después de la lista enlazada a un gran número de veces.
La manera más eficiente de hacerlo con más memoria, sería poner los punteros a los elementos de la matriz y, ordenarla, y luego buscar una repetición.
Otros consejos
Paso 1: , proceda de la manera habitual, que va a utilizar para encontrar el bucle, es decir, Tiene dos punteros, variación de una unidad en un solo paso y otra en dos pasos, si los dos se reúnen en algún momento, hay un bucle.
Paso 2: Congelar un puntero donde estaba e incrementar el puntero otros en un solo paso contando los pasos que realice y cuando ambos se encuentran de nuevo, el recuento le dará la longitud del bucle (esto es el mismo que el recuento del número de elementos en una lista enlace circular).
Paso 3: Restablecer ambos punteros al comienzo de la lista de enlaces, incrementar un puntero a la duración de los tiempos de bucle y luego iniciar el segundo puntero. incrementar ambos punteros en un solo paso y cuando se encuentran de nuevo, que será el inicio del bucle (esto es igual que la búsqueda de la n elemento º desde el final de la lista de enlaces).
prueba matemática + LA SOLUCIÓN
Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.
CASE simple: cuando k
Cuando puntero 'P' estaría en BEGINLOOP (es decir, que habría viajado pasos 'K'), Q habría viajado pasos '2k. Así, efectivamente, Q está por delante de los pasos de 2k-k = k 'de P cuando P entra en el bucle, y por lo tanto, Q es 'n-k' pasos detrás del BEGINLOOP ahora.
Cuando P se habría movido desde BEGINLOOP a MEETPONT, habría viajado pasos 'm-K'. En ese momento, habría viajado Q '2 (m-k)' pasos. Sin embargo, desde que se conocieron y comenzaron Q 'n-k' pasos detrás del BEGINLOOP, por lo que, efectivamente, '2 (m-k) - (n-k)' debe ser igual a '(m-k)' Por lo tanto,
=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m
Eso significa, P y Q se encuentran en el punto igual al número de pasos (o múltiple para ser general, véase el caso mencionado más adelante) en el bucle. Ahora, en el Punto de Encuentro, tanto P y Q son 'N- (m-k)' pasos detrás, es decir, pasos 'K' detrás, como vimos n = m. Por lo tanto, si partimos de la cabecera P de nuevo, y Q desde el Punto de Encuentro, pero esta vez con el ritmo igual a P, P y Q será ahora reunidos en BEGINLOOP solamente.
caso general: Say, k = nX + Y, Y
Cuando puntero 'P' estaría en BEGINLOOP (es decir, que habría viajado pasos 'K'), Q habría viajado pasos '2k. Así, efectivamente, Q está por delante de los pasos de 2k-k = k 'de P cuando P entra en el bucle. Sin embargo, tenga en cuenta 'k' es mayor que 'n', lo que significa Q habría hecho múltiples rondas de bucle. Así que, efectivamente, Q es 'n- (k)% n' pasos detrás del BEGINLOOP ahora.
Cuando P se habría movido desde BEGINLOOP a Punto de Encuentro, habría viajado pasos 'm-K'. (Por lo tanto, efectivamente, Punto de Encuentro estaría en '(m-k)% n' pasos por delante de BEGINLOOP ahora.) En aquel tiempo, Q habría viajado '2 (m-k)' pasos. Sin embargo, desde que se conocieron y comenzaron Q 'n- (k% n)' pasos detrás del BEGINLOOP, por lo que, efectivamente, la nueva posición de Q (que es '(2 (MK) - (nk /% n))% n 'de BEGINLOOP) debe ser igual a la nueva posición de P (que es '(mk)% n' de principio LOOP).
Por lo tanto,
=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'
En primer lugar tratamos de averiguar, ¿hay algún lazo en la lista o no. Si existe bucle después tratamos de averiguar el punto de bucle inicial. Para ello se utilizan dos punteros a saber slowPtr y fastPtr. En primera detección (comprobación de bucle), fastPtr mueve dos pasos a la vez pero slowPtr mueve por un paso por delante a la vez.
slowPtr 1 2 3 4 5 6 7 fastPtr 1 3 5 7 9 5 7
Está claro que si hay algún lazo en la lista a continuación, se reunirán en el punto (punto 7 en la imagen), porque puntero fastPtr se está ejecutando dos veces más rápido que el otro.
Ahora, llegamos al segundo problema de encontrar el punto de partida de bucle.
Supongamos, se reúnen en el punto 7 (como se ha mencionado en la imagen). Entonces, slowPtr sale del bucle y se sitúa en el comienzo de la lista significa que en el punto 1, pero fastPtr todavía en el punto de reunión (punto 7). Ahora comparamos los dos punteros de valor, si mismo, entonces es punto de partida de bucle de otro modo nos movemos un paso a delante (en este caso fastPtr también se está moviendo en un paso cada vez) y comparar de nuevo hasta que encontremos mismo punto.
slowPtr 1 2 3 4 fastPtr 7 8 9 4
Ahora bien, una pregunta viene a la mente, ¿cómo es posible. Así que hay una buena prueba matemática.
Supongamos que:
m => length from starting of list to starting of loop (i.e 1-2-3-4) l => length of loop (i.e. 4-5-6-7-8-9) k => length between starting of loop to meeting point (i.e. 4-5-6-7) Total distance traveled by slowPtr = m + p(l) +k where p => number of repetition of circle covered by slowPtr Total distance traveled by fastPtr = m + q(l) + k where q => number of repetition of circle covered by fastPtr Since, fastPtr running twice faster than slowPtr Hence, Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr i.e m + q(l) + k = 2 * ( m + p(l) +k ) or, m + k = q(l) - p(l) or, m + k = (q-p) l or, m = (q-p) l - k So, If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4) and fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4), because "(q-p) l" is a complete circle length with " (q-p) " times.
Se procede de la forma habitual que va a utilizar para encontrar el bucle. es decir. Tiene dos punteros, variación de una unidad en un solo paso (slowPointer) y otra en dos pasos (fastPointer), si ambos se encuentran en algún momento, hay un bucle.
Como se puede ya habría dado cuenta de que es punto de encuentro k paso antes de que el jefe del bucle.
donde k es el tamaño de la parte no-bucle de la lista.
ahora mover lento para la cabeza del bucle
mantener rápido en el punto de colisión
cada uno de ellos son k paso desde el inicio del bucle (Slow desde el inicio de la lista donde tan rápido es k paso antes de la cabeza de la loop- Dibujar el pic para obtener la claridad)
Ahora que moverse a la misma velocidad - Deben perseguir al inicio del bucle
por ejemplo
slow=head
while (slow!=fast)
{
slow=slow.next;
fast=fast.next;
}
Este es el código para encontrar inicio de bucle en la lista enlazada:
public static void findStartOfLoop(Node n) {
Node fast, slow;
fast = slow = n;
do {
fast = fast.next.next;
slow = slow.next;
} while (fast != slow);
fast = n;
do {
fast = fast.next;
slow = slow.next;
}while (fast != slow);
System.out.println(" Start of Loop : " + fast.v);
}
Existen dos vías para encontrar los bucles en una lista de enlaces. 1. El uso de dos punteros, uno avance un paso y otro avance dos pasos si hay bucle, en algún momento, tanto puntero obtener el mismo valor y nunca llegar a nulo. Pero si no hay un puntero de bucle llega a cero en un punto y tanto puntero nunca consigue el mismo valor. Sin embargo, en este enfoque podemos llegar es un bucle en la lista de enlaces, pero no podemos decir dónde exactamente a partir del bucle. Esta no es la manera eficiente.
- Utilice una función hash de tal manera que el valor debe ser único. En caso que si estamos tratando de insertar el duplicado se debe a través de la excepción. A continuación, viajar a través de cada nodo y la dirección de empuje en la tabla hash. Si el alcance puntero a NULL y no es una excepción a partir del hash significa que no hay ciclo en la lista de enlaces. Si estamos recibiendo ninguna excepción de hachís significa que hay un ciclo en la lista y que es el enlace desde el que el ciclo se está iniciando.
Bueno, yo probé una manera mediante el uso de un puntero ... He probado el método en varios conjuntos de datos .... Como la memoria de cada uno de los nodos de una lista enlazada se asignan en orden creciente, por lo que al atravesar la lista enlazada de la cabeza de la lista enlazada, si la dirección de un nodo se hace mayor que la dirección del nodo al que hace referencia, podemos determinar que hay un bucle, así como el elemento de inicio del bucle.
La mejor respuesta que he encontrado era aquí:
tianrunhe: hallazgo loop-punto de partida-in-a-circular--lista enlazada
- 'm' siendo la distancia entre la cabeza y START_LOOP
- 'L' siendo la longitud del bucle
- 'd' es la distancia entre MEETING_POINT y START_LOOP
-
p1 se mueve a V, y p2 se mueve a 2 * V
cuando el 2 punteros se encuentran: distancia recorrida es = * L m + n -d = 2 * (m + -d L)
=> Lo que significa (no mathematicaly demostrado aquí) que si se inicia desde p1 y p2 CABEZA inicia desde MEETING_POINT y se mueven al mismo ritmo, se reunirán @ START_LOOP
Consulte este enlace de respuesta completa.
-
Se procede de la forma habitual que va a utilizar para encontrar el bucle. es decir. Tiene dos punteros, variación de una unidad en un solo paso y otra en dos pasos, si los dos se reúnen en algún momento, hay un bucle.
-
Tenga uno de los punteros fijado obtener el número total de nodos en el bucle decir L.
-
Ahora desde este punto (incremento segundo puntero al siguiente nodo en el bucle) en el bucle de revertir la lista enlazada y contar el número de nodos atravesados, digamos X.
-
Ahora, utilizando el segundo puntero (bucle se rompe) desde el mismo punto en el bucle travrse la lista enlazada y contar el número de nodos restantes dicen Y
-
El bucle comienza después de la (-L (X + Y)) \ 2 nodos. O se inicia en el (((X + Y) -L) \ 2 + 1) ésimo nodo.
-
Se procede de la forma habitual que va a utilizar para encontrar el bucle. es decir. Tiene dos punteros, variación de una unidad en un solo paso y otra en dos pasos, si los dos se reúnen en algún momento, hay un bucle.
-
Tenga uno de los punteros fijado obtener el número total de nodos en el bucle decir L.
-
Ahora desde este punto (incremento segundo puntero al siguiente nodo en el bucle) en el bucle de revertir la lista enlazada y contar el número de nodos atravesados, digamos X.
-
Ahora, utilizando el segundo puntero (bucle se rompe) desde el mismo punto en el bucle travrse la lista enlazada y contar el número de nodos restantes dicen Y
-
El bucle comienza después de la (-L (X + Y)) \ 2 nodos. O se inicia en el (((X + Y) -L) \ 2 + 1) ésimo nodo.
void loopstartpoint(Node head){
Node slow = head.next;;
Node fast = head.next.next;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast){
System.out.println("Detected loop ");
break;
}
}
slow=head;
while(slow!=fast){
slow= slow.next;
fast = fast.next;
}
System.out.println("Starting position of loop is "+slow.data);
}
- detectar bucle
- copiar la dirección de cada elemento en el conjunto. Si no se encuentra duplicado ese es el inicio del bucle
