２つの連結リストが交差しているかどうかをJavaでどのように判断しますか？

2年 ago
光, 明
1 minute

2 つの連結リストが交差しているかどうかを判断する方法は、二重ポインタを使用する方法です。具体的な手順は次のとおりです。

  1. 1 番目の連結リストの先頭のノードを指すポインタ p1 と2 番目の連結リストの先頭のノードを指すポインタ p2 を定義します。
  2. リスト 1 とリスト 2 を同時に見ていき、p1 と p2 が指すノードが同じであれば、リストが交差していることを示し、True を返します。
  3. リスト1とリスト2の両方を最後まで辿っても共通ノードを見つけられなかった場合は、リストが重複していないことを示し、falseを返します。
  4. p1とp2を毎回ノード一つ分後に移動させて、リスト1とリスト2のトラバースを完了する。

サンプルコードの実装例を次に示します。

public class LinkedListIntersection {
    public static boolean isIntersect(ListNode head1, ListNode head2) {
        ListNode p1 = head1;
        ListNode p2 = head2;
        
        while (p1 != p2) {
            p1 = (p1 == null) ? head2 : p1.next;
            p2 = (p2 == null) ? head1 : p2.next;
        }
        
        return p1 != null;
    }
}

上記のコードでは、ListNodeはリストノードのクラスで、valueと次のノードを指すポインタnextを含む。isIntersect()メソッドは2つのリンクリストの先頭ノードを引数として受け取り、2つのリストに共通するノードがある場合はTrue、さもない場合はFasleを返す。

bannerAds