Red de conocimiento informático - Material del sitio web - ¿Cómo determinar si hay un ciclo en una lista enlazada individualmente?

¿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