¿Cómo funciona el enfoque de punteros lentos y rápidos de Floyd?

Hemos discutido los algoritmos de puntero rápido y lento de Floyd en Detectar bucle en una lista enlazada .El algoritmo consiste en iniciar dos punteros, lento y rápido desde el encabezado de la lista enlazada. Nos movemos lento un Node a la vez y rápido dos Nodes a la vez. Si hay un bucle, definitivamente se encontrarán. Este enfoque funciona debido a los siguientes hechos. 1) Cuando el puntero lento entra en el bucle, el puntero rápido debe estar dentro del bucle. Deje que el puntero rápido esté a una distancia k del lento. 2) Ahora, si consideramos los movimientos de punteros lentos y rápidos, podemos notar que la distancia entre ellos (de lento a rápido) aumenta en uno después de cada iteración. Después de una iteración (de lento = siguiente de lento y rápido = siguiente de rápido), la distancia entre lento y rápido se convierte en k+1, después de dos iteraciones, k+2, y así sucesivamente. Cuando la distancia se convierte en n, se encuentran porque se mueven en un ciclo de longitud n. Por ejemplo, podemos ver en el siguiente diagrama, la distancia inicial es 2. Después de una iteración,

Prueba alternativa:

• Démosle un índice a todos los Nodes del bucle a partir de 0

El índice se asigna a cada Node del bucle.

• Deje que la longitud del bucle sea L
• Observemos el movimiento del puntero lento desde el comienzo del ciclo junto con las iteraciones.

De la tabla, podemos decir que

Índice del Node señalado por el puntero lento después de la iteración i = i mod L

• Observemos el movimiento del puntero rápido desde el comienzo del ciclo junto con las iteraciones.

De la tabla, podemos decir que 

Índice del Node apuntado por Fast pointer después de la iteración i = ( 2 xi ) mod L

• Una cosa a tener en cuenta es que, para cuando el puntero lento llegue al comienzo del bucle, el puntero rápido estará a d Nodes del comienzo del bucle.
• 0 <= d <= L-1

En el momento en que el puntero lento llega al comienzo del bucle, el puntero rápido está a d Nodes del comienzo del bucle.

• Por lo tanto, para todas las iteraciones consecuentes también, el puntero rápido estará a d Nodes del Node que apuntaría si comenzara desde el principio del bucle
• Por lo tanto, tenemos
  el índice del Node apuntado por el puntero rápido después de la iteración i = ( ( 2 xi ) + d ) mod L

Ahora tenemos ambas ecuaciones:

• Índice del Node señalado por el puntero lento después de la iteración i = i mod L
• Índice del Node apuntado por Puntero rápido después de la iteración i = ( ( 2 xi ) + d ) mod L

Ahora asigne i = c , donde c = L – d

L – Longitud del bucle

d – distancia entre el puntero Rápido y el comienzo del ciclo, cuando el puntero Lento alcanza el comienzo del ciclo

Como 0 <= d <= L-1 , implica   1 <= c <= L

• Índice del Node apuntado por el puntero lento después de la iteración i = i mod L
                                                                                                 = c mod L
                                                                                                 = 0 , (si c = L )
                                                                                                     c , (si c < L )
• Índice del Node apuntado por Puntero rápido después de la iteración i = ( ( 2 xi ) + d ) mod L
                                                                                                 = ( ( 2 xc ) + d ) mod L
                                                                                                 = ( 2c + d ) mod L
                                                                                                 = ( c + c + d ) mod L
                                                                                                 = ( c + L ) mod L , ya que c = L – d , implica c + d = L
                                                                                                 = c mod L
                                                                                                 = 0 , ( si c = L )
                                                                                                    c , ( si c < L )
• Ahora tanto el puntero lento como el puntero rápido apuntan al mismo Node
• Por lo tanto probado

 ¿Cómo funciona el algoritmo de eliminación de ciclos? Consulte el método 3 de Detectar y eliminar bucles en una lista vinculada

// Java program to detect loop in a linked list
class LinkedList {
    Node head; // head of list
 
    /* Linked list Node*/
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                Put in the data*/
        Node new_node = new Node(new_data);
 
        /* 3. Make next of new Node as head */
        new_node.next = head;
 
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
 
    void detectLoop()
    {
        Node slow_p = head, fast_p = head;
        int flag = 0;
        while (slow_p != null && fast_p != null
            && fast_p.next != null) {
            slow_p = slow_p.next;
            fast_p = fast_p.next.next;
            if (slow_p == fast_p) {
                flag = 1;
                break;
            }
        }
        if (flag == 1)
            System.out.println("Loop found");
        else
            System.out.println("Loop not found");
    }
 
    /* Driver program to test above functions */
    public static void main(String args[])
    {
        LinkedList llist = new LinkedList();
 
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(10);
 
        /*Create loop for testing */
        llist.head.next.next.next.next = llist.head;
 
        llist.detectLoop();
    }
}

// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;
 
/* Link list node */
class Node {
public:
    int data;
    Node* next;
};
 
void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = new Node();
 
    /* put in the data */
    new_node->data = new_data;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
int detectLoop(Node* list)
{
    Node *slow_p = list, *fast_p = list;
 
    while (slow_p && fast_p && fast_p->next) {
        slow_p = slow_p->next;
        fast_p = fast_p->next->next;
        if (slow_p == fast_p) {
            return 1;
        }
    }
    return 0;
}
 
/* Driver code*/
int main()
{
    /* Start with the empty list */
    Node* head = NULL;
 
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 10);
 
    /* Create a loop for testing */
    head->next->next->next->next = head;
    if (detectLoop(head))
        cout << "Loop found";
    else
        cout << "No Loop";
    return 0;
}

<script>
 
// Javascript program to detect loop in a linked list
let head; // head of list
 
/* Linked list Node*/
class Node
{
    constructor(d)
    {
        this.data = d;
        this.next = null;
    }
}
 
/* Inserts a new Node at front of the list. */
function push(new_data)
{
     
    /* 1 & 2: Allocate the Node &
            Put in the data*/
    let new_node = new Node(new_data);
 
    /* 3. Make next of new Node as head */
    new_node.next = head;
 
    /* 4. Move the head to point to new Node */
    head = new_node;
}
 
function detectLoop()
{
    let slow_p = head, fast_p = head;
    let flag = 0;
     
    while (slow_p != null && fast_p != null &&
        fast_p.next != null)
    {
        slow_p = slow_p.next;
        fast_p = fast_p.next.next;
        if (slow_p == fast_p)
        {
            flag = 1;
            break;
        }
    }
    if (flag == 1)
        document.write("Loop found<br>");
    else
        document.write("Loop not found<br>");
}
 
// Driver code
push(20);
push(4);
push(15);
push(10);
 
// Create loop for testing
head.next.next.next.next = head;
 
detectLoop();
 
 
</script>

# Python program to detect loop in the linked list
 
# Node class
 
 
class Node:
 
    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
 
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    # Function to insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
 
    # Utility function to print it the linked LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print temp.data,
            temp = temp.next
 
    def detectLoop(self):
        slow_p = self.head
        fast_p = self.head
        while(slow_p and fast_p and fast_p.next):
            slow_p = slow_p.next
            fast_p = fast_p.next.next
            if slow_p == fast_p:
                return
 
 
# Driver program for testing
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(10)
 
# Create a loop for testing
llist.head.next.next.next.next = llist.head
if(llist.detectLoop()):
    print "Found Loop"
else:
    print "No Loop"

// C# program to detect loop in a linked list
using System;
 
public class LinkedList {
    Node head; // head of list
 
    /* Linked list Node*/
    public class Node {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                Put in the data*/
        Node new_node = new Node(new_data);
 
        /* 3. Make next of new Node as head */
        new_node.next = head;
 
        /* 4. Move the head to point to new Node */
        head = new_node;
    }
 
    Boolean detectLoop()
    {
        Node slow_p = head, fast_p = head;
        while (slow_p != null && fast_p != null
            && fast_p.next != null) {
            slow_p = slow_p.next;
            fast_p = fast_p.next.next;
            if (slow_p == fast_p) {
                return true;
            }
        }
        return false;
    }
 
    /* Driver code */
    public static void Main(String[] args)
    {
        LinkedList llist = new LinkedList();
 
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(10);
        /*Create loop for testing */
        llist.head.next.next.next.next = llist.head;
 
        Boolean found = llist.detectLoop();
        if (found) {
            Console.WriteLine("Loop Found");
        }
        else {
            Console.WriteLine("No Loop");
        }
    }
}

Loop found