Solución de Linked List Cycle

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

Ivo Zayas

student•

eso no se me habría ocurrido ni en mil años

Miguel Angel Reyes Moreno

student•

Por eso estamos aquí para aprender :D

Yojan Antonio Pardo Zabala

student•

Yo que había pensado que los nodos tuvieran índices lo cual acabaría con la eficiencia de las listas enlazadas xd

REYNALDO FABIAN NORIEGA ZAMBRANO

student••

Mi aporte en C++. Prefiero implementar la LL primero en lugar de usar std::list, ya que std::list no me permite crear facilment un ciclo dentro de la lista. Ademas esto es un espacio academico :D

#include<iostream>
#include<vector>


class Node{
public:
	int val;
	Node *next;
};


bool is_cyclic(Node *&list){

	if(!list) return false;

	Node *head =  list;
	Node *head2 = list;

	while(head2 && head2->next){
		head =  head->next;
		head2 = head2->next->next;

		if(head == head2) return true;

	}

	return false;
}



int main(){

	Node *head = new Node;
	Node *current = head;
	Node *loop;
	std::vector vals = {3,2,0,-4};

	for(int a: vals){
		current->val = a;
		current->next = new Node;
		if(current->val == 2){
			loop = current;
		}
		current = current->next;
	}
	current->next = loop;
	current = head;

	if(is_cyclic(head)){
		std::cout << "it is cyclic" <<std::endl;
	}
	else std::cout << "it is not" <<std::endl;


	return 0;
}

Bryan Castano

student•

TWO POINTERS :

struct Node * slow , * fast ;

slot = fast = head ;

while ( fast != NULL && fast->next != NULL ) {

slow = slow->next ;

fast = fast->next->next ;

if ( slow == fast )

return ( 1 ) ,

else

return ( 9) ;

//Como ELLa lo ha Explicado es muy Intuitivo y Revelador .\n

Nicolas Alpargatero

student•

En la clase anterior, no había considerado que podia haber ciclos dentro de la LL y no necesariamente hasta el final. . No sé cuántas veces lo repetí, pero quedó más claro, la solución con el playground.

Solución de Linked List Cycle

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

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Playground: 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

Playground: Reorder List Without Repeated Values

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

Playground: 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

Playground: K Closest Points to Origin

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de Reorganize String

Playground: 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