Linked List Cycle: análisis del problema

Cursos Empresas Blog Live Conf Precios

Contenido del curso

Introducción

1
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
00:52 min

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos

41
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
00:33 min

Tomar examen

Linked List Cycle: análisis del problema

Comentarios

Nicolas Alpargatero

Estudiante

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

Estudiante

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

Estudiante

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

Estudiante

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

William Rodriguez

Estudiante

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

Estudiante

y Una lista ciclica no tiene fin.

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada

Programando listas enlazadas con Java

Cómo Invertir una Lista Enlazada

Odd Even Linked List: análisis del problema

Solución de Odd Even Linked List

Playground: Odd Even Liked List

Programando Odd Even Linked List con C++