Playground: Linked List Cycle

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

Clase anteriorSiguiente clase

John Eduard Meneses González

student•

My Solution!!

Carlos Hernandez

student•

Yo agregué una propiedad booleana a la clase Nodo, para saber si cada nodo ya ha sido visitado previamente. Aquí mi solución:class Nodo: def __init__(self, x): self.valor = x self.siguiente = None self.visitado = False def hasCycle(cabeza: Nodo) -> bool: nodo = cabeza while nodo is not None: if not nodo.visitado: nodo.visitado = True nodo = nodo.siguiente else: return True return False nodo1 = Nodo(1)nodo2 = Nodo(2)nodo3 = Nodo(3)nodo4 = Nodo(4)nodo1.siguiente = nodo2nodo2.siguiente = nodo3nodo3.siguiente = nodo4nodo4.siguiente = nodo2 response = hasCycle(nodo1)print(response)

class Nodo:
   def __init__(self, x):
      self.valor = x
      self.siguiente = None
      self.visitado = False

def hasCycle(cabeza: Nodo) -> bool:
   nodo = cabeza
   while nodo is not None:
      if not nodo.visitado:
         nodo.visitado = True
         nodo = nodo.siguiente
      else:
         return True

   return False

nodo1 = Nodo(1)
nodo2 = Nodo(2)
nodo3 = Nodo(3)
nodo4 = Nodo(4)
nodo1.siguiente = nodo2
nodo2.siguiente = nodo3
nodo3.siguiente = nodo4
nodo4.siguiente = nodo2

response = hasCycle(nodo1)
print(response)

Bryan Castano

student•

My COde @Here [Bellow ] \n\n\n

class Nodo:
   def __init__(self, x):
      self.valor = x
      self.siguiente = None

def hasCycle(cabeza: Nodo) -> bool:
   # Tu código aquí 👇......

   if not cabeza :

      return False 

   slow = fast = cabeza 

   while ( fast is not None and fast.siguiente is not None ) : 

      slow = slow.siguiente 
      fast = fast.siguiente.siguiente 

      if ( slow == fast ) :

         return True 

   return False
  
```class Nodo:   def \_\_init\_\_(self, x):      self.valor = x      self.siguiente = None
def hasCycle(cabeza: Nodo) -> bool:   # Tu código aquí 👇......
&#x20;  if not cabeza :
&#x20;     return False&#x20;
&#x20;  slow = fast = cabeza&#x20;
&#x20;  while ( fast is not None and fast.siguiente is not None ) :&#x20;
&#x20;     slow = slow.siguiente       fast = fast.siguiente.siguiente&#x20;
&#x20;     if ( slow == fast ) :
&#x20;        return True&#x20;
&#x20;  return False

Miguel Angel Reyes Moreno

student•

Comparto mi solución:

def hasCycle(self, head: Optional\[ListNode]) -> bool:        if not head:            return False
&#x20;       slow = head        fast = head
&#x20;       while fast is not None and fast.next is not None:            slow = slow.next            fast = fast.next.next
&#x20;           if slow == fast:                return True
&#x20;       return False

Nicolas Alpargatero

student•

Siguiendo lo que dijo la profe:

Miguel Angel Reyes Moreno

student•

Creo que debiste esperar a que el confeti desapareciera para tomar el screenshot

Yojan Antonio Pardo Zabala

student•

aqui dejo mi solución, en esta oportunidad me pareció interesante utilizar el warus operator para hacer la asiganción de los apuntadores en la misma validación del while.

def hasCycle(cabeza: Nodo) -> bool:
   turtle = cabeza
   rabbit = cabeza
   while (turtle := turtle.siguiente) and rabbit.siguiente and (rabbit := rabbit.siguiente.siguiente):
      if turtle == rabbit:
         return True
   return False

Yojan Antonio Pardo Zabala

student•

aquí dejo mi solución, utilicé el walrus operator para realizar las asignaciones de los apuntadores durante la validación del while.

def hasCycle(cabeza: Nodo) -> bool:
   turtle = cabeza
   rabbit = cabeza
   while (turtle := turtle.siguiente) and rabbit.siguiente and (rabbit := rabbit.siguiente.siguiente):
      if turtle == rabbit:
         return True
   return False

Nicolas Guillen

student•

Como desarrollador de js, hoy aprendí que los if de Python se ejecutan al mismo tiempo en lugar de izquierda a derecha. Y que Python no tiene optional chaining en los objetos 💀

Hans Arias

student•

Mi solución fue si la cola (tail) es igual al Nodo que se esta iterando en el loop detener el ciclo, esta es mi solución en Java .

package org.example.circularloop;

public class LinkedListCircular {

    static Node head, tail;

    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    void push (int data) {
        Node currentNode = new Node(data);

        if (tail == null) {
            tail = currentNode;
            head = currentNode;
        }

        currentNode.next = head;
        head = currentNode;

        tail.next = head;
    }

    void print () {
        Node iteration = head;
        while (true) {
            System.out.print(iteration.data + " ");

            if (hasCycle() && iteration.equals(tail)) {
                break;
            }

            iteration = iteration.next;
        }

        System.out.println();
    }

    private boolean hasCycle () {
        return tail != null && tail.next != null;
    }

    public static void main(String[] args) {
        LinkedListCircular circular = new LinkedListCircular();

        circular.push(1);
        circular.push( 2);
        circular.push(3);
        circular.push(4);

        circular.print();
    }

}

<code>

Pro Code

student•

Para mi solución cree una variable estática longitud, para saber la cantidad de nodos agregados a la lista enlazada:

class Nodo:
   longitud = 0
   def __init__(self, x):
      self.valor = x
      self.siguiente = None
      Nodo.longitud += 1

def hasCycle(cabeza: Nodo) -> bool:
   actual = cabeza
   for i in range (cabeza.longitud):
      if (actual.siguiente == None):
            return False
      actual = actual.siguiente
   return True