Comment résoudre : erreur de structure de données Java : boucle de liste chaînée

Comment résoudre : erreur de structure de données Java : boucle de liste chaînée

Introduction :
Dans la programmation Java, les listes chaînées sont souvent utilisées comme structure de données pour stocker et manipuler des données. Cependant, une erreur courante se produit parfois lors des opérations de liste chaînée : les boucles de liste chaînée. Un cycle de liste chaînée signifie qu'un nœud de la liste chaînée pointe vers le nœud précédent ou le nœud suivant dans la liste chaînée, ce qui empêche le parcours correct de la liste chaînée. Cet article explique comment résoudre ce problème et fournit des exemples de code.

Analyse du problème :
Les boucles de liste chaînée sont généralement causées par la référence du nœud de la liste chaînée pointant vers le mauvais emplacement. Cela peut être dû à des erreurs de codage, à des erreurs de logique ou à d'autres raisons. Avant de résoudre ce problème, jetons un coup d'œil à un exemple de code :

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

public class LinkedList {
    Node head;
    
    public void add(int data) {
        Node newNode = new Node(data);
        
        if(head == null) {
            head = newNode;
        } else {
            Node current = head;
            
            while(current.next != null) {
                current = current.next;
            }
            
            current.next = newNode;
        }
    }
}

Le code ci-dessus est une simple implémentation de liste chaînée, qui contient une classe Node pour représenter les nœuds et une LinkedList<. /code >Class représente une liste chaînée. Dans la méthode <code>add, le nouveau nœud sera ajouté à la fin de la liste chaînée. Node类表示节点，以及一个LinkedList类表示链表。在add方法中，新节点会被添加到链表的末尾。

问题解决：
要解决链表循环的问题，我们需要检查链表中是否存在循环，并找到循环的位置。可以使用快慢指针的方法来实现。

快慢指针法的基本思想是将两个指针放在链表的头部，一个指针每次移动一步，另一个指针每次移动两步。如果链表中存在循环，则快指针最终将追上慢指针。

下面我们来修改LinkedList类的代码，添加一个hasCycle方法来检查链表是否存在循环：

public class LinkedList {
    Node head;
    
    public boolean hasCycle() {
        Node fast = head;
        Node slow = head;
        
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            
            if(fast == slow) {
                return true;
            }
        }
        
        return false;
    }
}

在hasCycle方法中，我们使用了快慢指针来检测链表中是否存在循环。如果存在循环，快慢指针最终会相遇，就说明链表中存在循环。

接下来，我们修改add方法，添加一个判断链表是否存在循环的逻辑：

public void add(int data) {
    Node newNode = new Node(data);
    
    if(hasCycle()) {
        throw new IllegalArgumentException("链表中存在循环");
    }
    
    if(head == null) {
        head = newNode;
    } else {
        Node current = head;
        
        while(current.next != null) {
            current = current.next;
        }
        
        current.next = newNode;
    }
}

在添加新节点之前，我们先调用hasCycle

Résolution de problèmes :

Pour résoudre le problème des boucles de liste chaînée, nous devons vérifier s'il y a une boucle dans la liste chaînée et trouver l'emplacement de la boucle. Ceci peut être réalisé en utilisant des pointeurs rapides et lents.

L'idée de base de la méthode du pointeur rapide et lent est de placer deux pointeurs en tête de la liste chaînée, un pointeur se déplace d'un pas à la fois et l'autre pointeur se déplace de deux pas à la fois. S'il y a un cycle dans la liste chaînée, le pointeur rapide finira par rattraper le pointeur lent.

Modifions le code de la classe LinkedList et ajoutons une méthode hasCycle pour vérifier s'il y a un cycle dans la liste chaînée :

rrreee
• Dans le hasCycle , nous utilisons des pointeurs rapides et lents pour détecter s'il y a un cycle dans la liste chaînée. S'il y a un cycle, les pointeurs rapide et lent finiront par se rencontrer, indiquant qu'il y a un cycle dans la liste chaînée.

Ensuite, nous modifions la méthode add et ajoutons une logique pour déterminer s'il y a un cycle dans la liste chaînée : 🎜rrreee🎜Avant d'ajouter un nouveau nœud, nous appelons d'abord le hasCycle méthode pour détecter s’il existe un cycle dans la liste chaînée. Si une boucle existe, lancez une exception et alertez l'utilisateur. 🎜🎜Conclusion : 🎜En utilisant la méthode des pointeurs rapides et lents, nous pouvons détecter efficacement s'il y a un cycle dans la liste chaînée et l'éviter lors de l'ajout de nœuds. Cet article fournit un exemple de code simple, dans l'espoir d'aider les lecteurs à mieux comprendre et résoudre le problème des boucles de listes chaînées. Bien entendu, dans le développement réel, nous devons également déboguer et optimiser en fonction de circonstances spécifiques pour garantir l'exactitude et les performances du code. 🎜🎜Référence : 🎜🎜🎜[https://leetcode.com/problems/linked-list-cycle/](https://leetcode.com/problems/linked-list-cycle/)🎜🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!