解決方法: Java データ構造エラー: リンクリストループ-＆＃＆チュートリアル-php.cn

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

WBOY

リリース： 2023-08-27 10:37:44

オリジナル

1214 人が閲覧しました

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

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

参考資料: