解決方法: Java データ構造エラー: リンク リスト ループ

解決方法: Java データ構造エラー: リンク リスト ループ

はじめに:
Java プログラミングでは、リンク リストは、保存するデータ構造としてよく使用されます。および運用データ。ただし、リンク リスト操作、つまりリンク リスト ループを処理するときに、よくある間違いが発生することがあります。リンク リスト サイクルとは、リンク リスト内のノードがリンク リスト内の前のノードまたは次のノードを指し、リンク リストが正しく走査されなくなることを意味します。この記事では、この問題を解決する方法を検討し、コード例を示します。

問題分析:
リンク リスト ループは、通常、間違った場所を指すリンク リスト ノードへの参照によって発生します。これは、コーディング エラー、論理エラー、またはその他の理由が原因である可能性があります。この問題を解決する前に、まずコード例を見てみましょう:

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;
        }
    }
}

上記のコードは単純なリンク リストの実装であり、ノードを表す Node クラスと LinkedList クラスはリンクされたリストを表します。 add メソッドでは、新しいノードがリンク リストの最後に追加されます。

問題解決策:
リンク リスト ループの問題を解決するには、リンク リストにループがあるかどうかを確認し、ループの場所を見つける必要があります。これは、高速ポインタと低速ポインタを使用して実現できます。

高速ポインタと低速ポインタ方式の基本的な考え方は、リンクされたリストの先頭に 2 つのポインタを配置し、1 つのポインタは一度に 1 ステップずつ移動し、もう 1 つのポインタは一度に 2 ステップ移動することです。 。リンクされたリストにサイクルがある場合、高速ポインタは最終的に低速ポインタに追いつきます。

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;
    }
}

in 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 メソッドを呼び出して、リンクされたリストにサイクルがあるかどうかを検出します。ループが存在する場合は、例外をスローしてユーザーに警告します。

結論:
高速ポインタと低速ポインタの方法を使用することにより、リンクされたリストにサイクルがあるかどうかを効果的に検出し、ノードを追加するときにサイクルを回避できます。この記事では、読者がリンク リスト ループの問題をよりよく理解し、解決できるようにするために、簡単なコード例を提供します。もちろん、実際の開発では、コードの正確性とパフォーマンスを確保するために、特定の状況に応じてデバッグや最適化を行う必要もあります。

参考資料:

• [https://leetcode.com/problems/linked-list-cycle/](https://leetcode.com/problems/linked-list -サイクル/）＃＃＃＃＃＃

以上が解決方法: Java データ構造エラー: リンク リスト ループの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。