Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

Optimize Node.has_loop to use constant auxiliary space instead of O(N) space

Abierto
  • ¿Algo no está bien?
#15,576 1 comentario 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

@mohitjoshi-hey ya está trabajando en esto.

Desde el 14/10/2026.

  • #1 de @Aarya1777 — cerrado sin fusionar
  • #15577 de @mohitjoshi-hey — abierto
  • #15578 de @xingzihai — abierto
  • #15587 de @Aarya1777 — cerrado sin fusionar
  • #15588 de @Aarya1777 — abierto
  • #15589 de @krishna2707 — abierto
  • #15607 de @iamshresthraj — abierto

Evaluación

Dificultad
2/5
Tiempo estimado
1-3 horas
Aptitud para principiantes
15/100
Tipo de issue
Refactorización
Claridad
Bien especificado
Estado de actividad
Estancado
Stack tecnológico
python
Área
backend

Línea de trabajo

The has_loop property in data_structures/linked_list/has_loop.py currently builds a set of visited nodes via the iterator. Linked PR #15577 is already open against this issue, so check that PR before starting, since the work is under way. The change would replace the set with Floyd's tortoise-and-hare pointers, and done means the listed cases pass: acyclic, self-loop, back-edge, tail loop, and duplicate data values.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

enhancement
Feature description

Optimize has_loop to use constant auxiliary space

Description

The has_loop property in data_structures/linked_list/has_loop.py currently detects loops by traversing the linked list and storing every visited node in a set:

@property
def has_loop(self) -> bool:
    try:
        list(self)
        return False
    except ContainsLoopError:
        return True

The iterator uses:

visited = set()

and adds each visited node to that set. As a result, detecting whether a linked list contains a loop requires O(n) additional memory.

Proposed change

Update only the has_loop property in:

data_structures/linked_list/has_loop.py

Use Floyd’s tortoise-and-hare cycle-detection algorithm:

  • A slow pointer moves one node at a time.
  • A fast pointer moves two nodes at a time.
  • If the pointers meet, the linked list contains a loop.
  • If the fast pointer reaches the end of the list, no loop exists.
Expected complexity
Time complexity:  O(n)
Auxiliary space: O(1)
Required behavior

The updated has_loop property should correctly detect:

  • an acyclic linked list;
  • a self-loop;
  • a loop back to an earlier node;
  • a loop involving the final node;
  • lists containing duplicate data values in different nodes.

Loop detection must compare node references rather than node data values.

Reference

Floyd’s cycle-finding algorithm

Lenguaje dominante
Python
Estrellas
225k
Forks
51.2k
Merge medio
1 d 8 h
PR fusionados (30 d)
40

Preparar el entorno

Abrir en Codespaces

Inicia el contenedor de desarrollo del proyecto en tu navegador, con tu propia cuenta de GitHub.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de TheAlgorithms/Python

Todos los issues de TheAlgorithms/Python

Issues similares

Más issues de Python

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.