Linked List Cycle: análisis del problema

Clase 9 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Clase anteriorSiguiente clase

Nicolas Alpargatero

student•

El problema solo dice determinar si hay un ciclo, sería con el tail si el next no es None es porque tiene alguno, normalmente es con el head

Said Josue Calixtro Maldonado

student•

Hola, esta es mi solución:

Si la LL contiene un Loop, significa que en algún momento pasamos dos veces por el mismo nodo. Entonces, podemos almacenar los nodos visitados en una hash table.
Si la LL no contiene un Loop, eventualmente llegaremos a un nodo vacío.

Siguiendo las reglas anteriores, los pasos serían:

Comenzamos con un apuntador p = head.
Inicializamos una hash table con los nodos visitados visited_nodes.
¿p está en visited_nodes?
- Sí: Entonces hay un loop y retornamos true.
Si no hemos visitado el nodo, entonces agregamos p como llave de visited_nodes.
Movemos el apuntador p = p.next.
Regresamos al paso 3 hasta que p == None (hemos terminado de recorrer la LL).
Si llegamos al caso de que p == None signidica que no hay loops, entonces retornamos false.

Irving Juárez

student•

Yo tengo una solución más sencilla. Iteramos por cada uno de los Nodos en un for loop y si algún Nodo.next es igual a null, entonces es falso. Si no es verdadero:

let current = linkedList.head
for(let i = 0; i < linkedList.size; i++) {
  if(!current.next) return false
  current = current.next
}

Juan Pablo Reina Gutierrez

student•

No sé si el problema es más complejo, pero yo lo veo algo tan sencillo como este método:

William Rodriguez

student•

eso no mira si tienes un ciclo solo es un if que mira si la cola es nula ósea si es el final de la lista.

William Rodriguez

student•

y Una lista ciclica no tiene fin.