Hacktoberfest 2026: die Issues, die Maintainer für den Oktober markiert haben – offen und einsteigerfreundlich. Hacktoberfest-Issues durchsuchen

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

Offen
  • Stimmt etwas nicht?
#15,576 1 Kommentar 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

@mohitjoshi-hey arbeitet bereits daran.

Seit 14.10.2026.

  • #1 von @Aarya1777 — ohne Merge geschlossen
  • #15577 von @mohitjoshi-hey — offen
  • #15578 von @xingzihai — offen
  • #15587 von @Aarya1777 — ohne Merge geschlossen
  • #15588 von @Aarya1777 — offen
  • #15589 von @krishna2707 — offen
  • #15607 von @iamshresthraj — offen

Bewertung

Schwierigkeit
2/5
Geschätzter Aufwand
1-3 Stunden
Anfängerfreundlichkeit
15/100
Issue-Typ
Refactoring
Klarheit
Klar beschrieben
Aktivitätsstatus
Veraltet
Tech-Stack
python
Bereich
backend

Rechercherichtung

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.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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

Vorherrschende Sprache
Python
Sterne
225k
Forks
51.2k
Ø Merge
1 T. 8 Std.
Gemergte PRs (30 T.)
40

Entwicklungsumgebung

In Codespaces öffnen

Startet den Dev-Container des Projekts im Browser, mit Ihrem eigenen GitHub-Konto.

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus TheAlgorithms/Python

Alle Issues in TheAlgorithms/Python

Ähnliche Issues

Weitere Issues zu Python

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.