¿Cómo determinar si hay un ciclo en una lista enlazada individualmente?
Dada una lista enlazada individualmente, intente determinar si hay un ciclo en la lista enlazada individualmente. Respuesta: La idea del algoritmo es establecer dos punteros p y q, donde p avanza un paso cada vez y q avanza dos pasos cada vez. Entonces, si hay un anillo en la lista enlazada individualmente, entonces p y q se encuentran; de lo contrario, q encontrará nulo primero; Supongamos que la longitud de la lista enlazada individualmente es n, y que la lista enlazada individualmente es cíclica, luego en la i-ésima iteración, p apunta al elemento i mod n y q apunta a 2i mod n. Por lo tanto, cuando i≡2i(mod n), p y q se encuentran. Y i≡2i(mod n) =gt; (2i - i) mod n = 0 =gt; i mod n = 0 =gt; Una comprensión simple aquí es que p y q están corriendo en el patio de recreo al mismo tiempo, donde la velocidad de q es el doble que la de p. Cuando ambos comienzan al mismo tiempo, p corre una vuelta hasta el punto de partida y q acaba de terminar. Completamos dos vueltas en este momento. Llegamos al punto de partida. Entonces, ¿qué sucede cuando p y q tienen diferentes puntos de partida? Supongamos que p apunta al elemento i mod n en la i-ésima iteración, y q apunta a k 2i mod n, donde 0