Programando Linked List Cycle con Python

Clase 12 de 41 • 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

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

Tomar examen

Comentarios

Juan Pablo Reina Gutierrez

student•

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

student•

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

student•

My Solution!!

Jose Manuel Florez

student•

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

student•

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

student•

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

student•

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;
}

Programando Linked List Cycle con Python

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++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Playground: Linked List Cycle