Ciclo en una lista enlazada 2

En este blog, te enseñaré cómo resolver el ejercicio Ciclo en una lista enlazada 2 de la plataforma LeetCode en Java, Python, PHP, C++ y JavaScript en español.

En esta guía, aprenderás a:

✅ Una explicación del problema
✅ Una solución eficiente
✅ Implementaciones en Java, Python, PHP, C++ y JavaScript

Este ejercicio se encuentra en la plataforma de LeetCode como "Linked List Cycle II".

                       
Problema
Dada una lista enlazada, devuelve el nodo donde comienza el ciclo, y si no hay, retorna nulo.



Pasos para realizar el algoritmo:
1.- Se crean dos punteros, lento y rápido, que se inicializan al mismo nodo que la cabeza de la lista.

2.- Se ejecuta un bucle mientras rápido y su siguiente posición no sean null.

3.- Dentro del bucle, se avanza un paso con lento y dos pasos con rápido esto se hace hasta que lleguen al mismo nodo.

4.1.-  Se reinicia lento a la cabeza de la lista.

4.2.-  Se avanza con lento y rápido al mismo tiempo hasta que se encuentren de nuevo. Este va a ser el inicio del ciclo

4.3.-  Se retorna el puntero lento, que es el puntero del inicio del ciclo.

Presentación

Código en Java

public class Solution {
  public ListNode detectCycle(ListNode cabeza) {
    //paso#1
    ListNode lento = cabeza;
    ListNode rapido = cabeza;
 
    //paso#2
    while (rapido != null && rapido.next != null) {
 
      //paso#3  
      lento = lento.next;
      rapido = rapido.next.next;
 
      //paso#4
      if (lento == rapido) {
 
        //paso#4.1  
        lento = cabeza;
        //paso#4.2
        while (lento != rapido) {
          lento = lento.next;
          rapido = rapido.next;
        }
 
        //paso#4.3
        return lento;
      }
    }
 
    //paso#5
    return null;
  }
}

Código en php

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
 
class Solution {
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function detectCycle($cabeza) {
        // Paso #1
        $lento = $cabeza;
        $rapido = $cabeza;
 
        // Paso #2
        while ($rapido != null && $rapido->next != null) {
            // Paso #3
            $lento = $lento->next;
            $rapido = $rapido->next->next;
 
            // Paso #4
            if ($lento === $rapido) {
                // Paso #4.1
                $lento = $cabeza;
 
                // Paso #4.2
                while ($lento !== $rapido) {
                    $lento = $lento->next;
                    $rapido = $rapido->next;
                }
 
                // Paso #4.3
                return $lento;
            }
        }
 
        // Paso #5
        return null;
    }
}

Código en Python

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
     
    class Solution(object):
        def detectCycle(self, head):
            # Paso #1
            lento = head
            rapido = head
     
            # Paso #2
            while rapido is not None and rapido.next is not None:
                # Paso #3
                lento = lento.next
                rapido = rapido.next.next
     
                # Paso #4
                if lento == rapido:
                    # Paso #4.1
                    lento = head
     
                    # Paso #4.2
                    while lento != rapido:
                        lento = lento.next
                        rapido = rapido.next
     
                    # Paso #4.3
                    return lento
     
            # Paso #5
            return None

Código en C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
 public:
  ListNode *detectCycle(ListNode *head) {
    // Paso #1
    ListNode *lento = head;
    ListNode *rapdio = head;
 
    // Paso #2
    while (rapdio != nullptr && rapdio->next != nullptr) {
      // Paso #3
      lento = lento->next;
      rapdio = rapdio->next->next;
 
      // Paso #4
      if (lento == rapdio) {
        // Paso #4.1
        lento = head;
 
        // Paso #4.2
        while (lento != rapdio) {
          lento = lento->next;
          rapdio = rapdio->next;
        }
 
        // Paso #4.3
        return lento;
      }
    }
 
    // Paso #5
    return nullptr;
  }
};

Código en JavaScript

/**
    * Definition for singly-linked list.
    * function ListNode(val) {
    *     this.val = val;
    *     this.next = null;
    * }
    */
    
   /**
    * @param {ListNode} head
    * @return {ListNode}
    */
   var detectCycle = function(head) {
       // Paso #1
     let lento = head;
     let rapido = head;
    
     // Paso #2
     while (rapido !== null && rapido.next !== null) {
       // Paso #3
       lento = lento.next;
       rapido = rapido.next.next;
    
       // Paso #4
       if (lento === rapido) {
         // Paso #4.1
         lento = head;
    
         // Paso #4.2
         while (lento !== rapido) {
           lento = lento.next;
           rapido = rapido.next;
         }
    
         // Paso #4.3
         return lento;
       }
     }
    
     // Paso #5
     return null;
    
   };

        
    
Conclusión
En este blog, hemos visto cómo realizar el ejercicio Linked List Cycle II en Java, Python, PHP, C++ y JavaScript.

Hemos visto ejemplos de código en cada lenguaje de programación.