Programando Linked List Cycle con Python

Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

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

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

Tomar examen

Cursos Empresas Blog Live Conf Eventos Precios

0:0010:28

Programando Linked List Cycle con Python

Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Clase 10 de 34

Clase 10 / 34

Comentarios (6)6 comentarios

Juan Pablo Reina Gutierrez

Hace 3 años

En el código de la profe solo hay un error en la línea 6 donde se indica el tipo de dato ya que es de tipo "Nodo" debido que la función recibe como parámetro el primer nodo de la lista. Y además como la función está fuera de la clase, no se debe incluir el parámetro "self":

Miguel Angel Reyes Moreno

Hace 2 años

Además de que no tiene sentido que en la línea 7 regrese "None" cuando explícitamente se define que la función regresa un bool. Debería regresar "False" en ese caso.

John Eduard Meneses González

Hace 2 años

My Solution!!

Jose Manuel Florez

Hace 2 años

esta es mi solución en java: ```java public boolean hasCycle (Nodo cabeza){

	boolean boolHasCycle = true;
	//voy a asumir que cada nodo tiene un único valor
	//entonces al comparar si ya se pasó por ese nodo compararé los valores que tienen dentro
	if(cabeza == null || cabeza.siguiente == null){
		return false;
	}

	Nodo apuntadorRapido = cabeza;
	Nodo apuntadorLento = cabeza;

	while (boolHasCycle) {

		if (apuntadorLento.siguiente != null){
			apuntadorLento = apuntadorLento.siguiente;
		}
		//este lo hago por si algo, pero en mi mente va a llegar siempre el rápido primero a null, en caso de existir un final
		else {
			boolHasCycle = false;
		}

		if (apuntadorRapido.siguiente != null) {
			if(apuntadorRapido.siguiente.siguiente != null){
				apuntadorRapido = apuntadorRapido.siguiente.siguiente;
			}
			else {
				boolHasCycle = false;
			}
		}
		else {
			boolHasCycle = false;
		}

		if(apuntadorRapido.valor == apuntadorLento.valor){
			break;
		}
	}

	return boolHasCycle;

}

Carlos Castro

Hace 2 años

En TypeScript:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {

    if (head == null) { return false }

    let p1 = head;
    let p2 = head.next; // Fast pointer

    while (p1 != p2) {

        if (!p2 || !p2.next) {
            return false;
        }
        p1 = p1.next;
        p2 = p2.next.next;

    }
    return true;

};
```/\*\* \* Definition for singly-linked list. \* class ListNode { \*     val: number \*     next: ListNode | null \*     constructor(val?: number, next?: ListNode | null) { \*         this.val = (val===undefined ? 0 : val) \*         this.next = (next===undefined ? null : next) \*     } \* } \*/
function hasCycle(head: ListNode | null): boolean {
&#x20;   if (head == null) { return false }
&#x20;   let p1 = head;    let p2 = head.next; // Fast pointer
&#x20;   while (p1 != p2) {
&#x20;       if (!p2 || !p2.next) {            return false;        }        p1 = p1.next;        p2 = p2.next.next;
&#x20;   }    return true;
};

Francisco Roberto Gomez

Hace 3 años

Lo había pensado como en la segundo versión de la profe pero agregue en el if que si lento estaba después de rápido arrojara true. Dejo mi ejecución en c++

template<class T> bool Lista<T>::hasCycle(){
    Nodo<T> *rapido=inicio;
    Nodo<T> *lento=inicio;

    if (inicio== nullptr){
        throw 404;
    }

    if (inicio->getSiguiente()== nullptr){
        return false;
    }

    while (rapido->getSiguiente()!= nullptr || rapido== nullptr){

        if (rapido->getSiguiente()==lento || rapido==lento){
            //hay algun ciclo
            return true;
        }

        lento=lento->getSiguiente();
        rapido=rapido->getSiguiente()->getSiguiente();
    }

    return false;
}

Nicolas Alpargatero

Hace 3 años

Me da curiosidad que dijo que lento y rápido iniciaban en el mismo, pero en la implementación no, aun así, ayudo bastante afianzar Linked List.

	boolean boolHasCycle = true;
	//voy a asumir que cada nodo tiene un único valor
	//entonces al comparar si ya se pasó por ese nodo compararé los valores que tienen dentro
	if(cabeza == null || cabeza.siguiente == null){
		return false;
	}

	Nodo apuntadorRapido = cabeza;
	Nodo apuntadorLento = cabeza;

	while (boolHasCycle) {

		if (apuntadorLento.siguiente != null){
			apuntadorLento = apuntadorLento.siguiente;
		}
		//este lo hago por si algo, pero en mi mente va a llegar siempre el rápido primero a null, en caso de existir un final
		else {
			boolHasCycle = false;
		}

		if (apuntadorRapido.siguiente != null) {
			if(apuntadorRapido.siguiente.siguiente != null){
				apuntadorRapido = apuntadorRapido.siguiente.siguiente;
			}
			else {
				boolHasCycle = false;
			}
		}
		else {
			boolHasCycle = false;
		}

		if(apuntadorRapido.valor == apuntadorLento.valor){
			break;
		}
	}

	return boolHasCycle;

}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {

    if (head == null) { return false }

    let p1 = head;
    let p2 = head.next; // Fast pointer

    while (p1 != p2) {

        if (!p2 || !p2.next) {
            return false;
        }
        p1 = p1.next;
        p2 = p2.next.next;

    }
    return true;

};
```/\*\* \* Definition for singly-linked list. \* class ListNode { \*     val: number \*     next: ListNode | null \*     constructor(val?: number, next?: ListNode | null) { \*         this.val = (val===undefined ? 0 : val) \*         this.next = (next===undefined ? null : next) \*     } \* } \*/
function hasCycle(head: ListNode | null): boolean {
&#x20;   if (head == null) { return false }
&#x20;   let p1 = head;    let p2 = head.next; // Fast pointer
&#x20;   while (p1 != p2) {
&#x20;       if (!p2 || !p2.next) {            return false;        }        p1 = p1.next;        p2 = p2.next.next;
&#x20;   }    return true;
};

template<class T> bool Lista<T>::hasCycle(){
    Nodo<T> *rapido=inicio;
    Nodo<T> *lento=inicio;

    if (inicio== nullptr){
        throw 404;
    }

    if (inicio->getSiguiente()== nullptr){
        return false;
    }

    while (rapido->getSiguiente()!= nullptr || rapido== nullptr){

        if (rapido->getSiguiente()==lento || rapido==lento){
            //hay algun ciclo
            return true;
        }

        lento=lento->getSiguiente();
        rapido=rapido->getSiguiente()->getSiguiente();
    }

    return false;
}

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

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Programando Palindrome Linked List con Java

Reorder List: análisis del problema

Solución de Reorder List

Programando Reorder List con JavaScript

Reto: LRU Caché

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Pilas y colas

Estructura de datos: Pilas y Colas

Paréntesis Válido: análisis del problema

Solución de Paréntesis Válido

Programando Paréntesis Válido con C++

Comparación de Cadenas con Backspaces

Colas de prioridad

Estructura de datos: Colas de Prioridad

K Closest Points to Origin: análisis del problema

Solución de K Closest Points to Origin

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de Reorganize String

Programando Reorganize String con Python

Colas de Prioridad: Ejercicios Prácticos y Soluciones

Colas de Prioridad y Gestión de Eventos

Próximos pasos

Toma el Curso Avanzado de Algoritmos: Grafos y Árboles

Programando Linked List Cycle con Python