algorithm - ultimo - eliminar un nodo de una lista enlazada en c++

Cómo determinar si una lista vinculada tiene un ciclo utilizando solo dos ubicaciones de memoria

Question

¿Alguien sabe de un algoritmo para encontrar si una lista vinculada gira sobre sí misma usando solo dos variables para atravesar la lista? Supongamos que tiene una lista vinculada de objetos, no importa qué tipo de objeto. Tengo un puntero al encabezado de la lista enlazada en una variable y solo tengo otra variable para recorrer la lista.

Así que mi plan es comparar los valores del puntero para ver si los punteros son iguales. La lista es de tamaño finito, pero puede ser enorme. Puedo establecer ambas variables a la cabeza y luego recorrer la lista con la otra variable, siempre comprobando si es igual a la otra variable, pero, si toco un bucle, nunca saldré de él. Estoy pensando que tiene que ver con diferentes tasas de atravesar la lista y comparar valores de puntero. ¿Alguna idea?

Answer 1

Absolutamente. Una solución puede atravesar la lista con ambos punteros, uno que viaja al doble de la velocidad del otro.

Comience con el puntero ''lento'' y ''rápido'' apuntando a cualquier ubicación en la lista. Ejecute el ciclo transversal. Si el puntero ''rápido'' en cualquier momento coincide con el puntero lento, tiene una lista circular vinculada.

int *head = list.GetHead();
if (head != null) {
int *fastPtr = head;
int *slowPtr = head;
bool isCircular = true;
do
{
if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
{
isCircular = false;
break;
}
fastPtr = fastPtr->Next->Next;
slowPtr = slowPtr->Next;
} while (fastPtr != slowPtr);
//Do whatever you want with the ''isCircular'' flag here
}

Answer 2

Llevar este problema al próximo paso será identificar el ciclo (es decir, no solo que el ciclo existe, sino dónde exactamente está en la lista). El algoritmo Tortoise and Hare se puede usar para lo mismo, sin embargo, necesitaremos hacer un seguimiento del encabezado de la lista en todo momento. Una ilustración de este algoritmo se puede encontrar here .

Answer 3

Puedes usar el algoritmo Turtle and Rabbit .

Wikipedia también tiene una explicación, y lo llaman " Algoritmo de búsqueda de ciclos de Floyd " o "Tortuga y liebre"

Answer 4

Traté de resolver esto por mi cuenta y encontré una solución diferente (menos eficiente pero aún óptima).

La idea se basa en invertir una lista enlazada en tiempo lineal. Esto se puede hacer haciendo dos intercambios en cada paso al iterar sobre la lista. Si q es el elemento anterior (inicialmente nulo) y p es el actual, entonces swap (q, p-> next) swap (p, q) invertirá el enlace y avanzará los dos punteros al mismo tiempo. Los intercambios pueden hacerse usando XOR para evitar tener que usar una tercera ubicación de memoria.

Si la lista tiene un ciclo, en un punto durante la iteración llegará a un nodo cuyo puntero ya ha sido cambiado. No puede saber qué nodo es, pero al continuar la iteración, intercambiando algunos elementos dos veces, vuelve a encabezar la lista.

Al invertir la lista dos veces, la lista se mantiene sin cambios en el resultado y puede decir si tenía un ciclo basado en si llegó al encabezado original de la lista o no.

Answer 5

Sugeriría usar Floyd''s Cycle-Finding Algorithm también conocido como La Tortoise and the Hare Algorithm . Tiene una complejidad O (n) y creo que se ajusta a sus necesidades.

Código de ejemplo:

function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}

Más información en Wikipedia: Algoritmo de búsqueda de ciclos de Floyd .

Answer 6

boolean findCircular(Node *head)
{
Node *slower, * faster;
slower = head;
faster = head->next;
while(true) {
if( !faster || !faster->next)
return false;
else if (faster == slower || faster->next == slower)
return true;
else{
faster = faster->next->next;
}
}
}

Answer 7

int isListCircular(ListNode* head){
if(head==NULL)
return 0;
ListNode *fast=head, *slow=head;
while(fast && fast->next){
if(fast->next->next==slow)
return 1;
fast=fast->next->next;
slow=slow->next;
}
return 0;
}