データ構造とアルゴリズム: リンクリストの交差、交差点を見つける

[[441326]]

リンクリストの交差

LeetCode の問題へのリンク: https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci

単一リンクリストの 2 つのヘッドノード headA と headB が指定されている場合、2 つの単一リンクリストが交差する開始ノードを見つけて返します。 2 つのリンクリストに交差がない場合は null を返します。

この図は、2 つのリンクリストがノード c1 で交差し始めていることを示しています。

タイトルデータにより、チェーン構造全体にループがないことが保証されます。

関数が返された後、リンクリストは元の構造を維持する必要があることに注意してください。

例1:

例2:

例3:

アイデア

簡単に言えば、2 つのリンクリストの交差ノードのポインタを見つけることです。ここで学生は、交差点は値が等しいのではなく、ポインタが等しいことに注意する必要があります。

例として、ノード要素の値が等しい場合、ノードポインターも等しいと想定します。

次の 2 つのリンクリストを見てください。現在、curA はリンクリスト A のヘッドノードを指し、curB はリンクリスト B のヘッドノードを指しています。

2 つのリンクリストの長さと 2 つのリンクリストの長さの差を計算し、図に示すように、curA を curB の末尾に一致する位置に移動します。

この時点で、curA と curB が同じかどうかを比較できます。同じでない場合は、curA と curB を同時に後方に移動します。curA == curB の場合、交差が見つかります。

それ以外の場合はループが終了し、null ポインターを返します。

C++ コードは次のとおりです。

クラスソリューション{
公共：
    リストノード *getIntersectionNode(リストノード *headA、リストノード *headB) {
        リストノード* curA = headA;
        リストノード* curB = headB;
整数lenA = 0、lenB = 0;
        while (curA != NULL ) { // リンクリストAの長さを見つける
            lenA++;
            curA = curA->次へ;
        }
        while (curB != NULL ) { // リンクリストBの長さを見つける
            lenB++;
            curB = curB->次へ;
        }
        curA = ヘッドA;
        カーソルB = ヘッドB;
        // curA を最長リンクリストの先頭とし、lenA をその長さとする
        （長さB＞長さA）の場合{
            （lenA、lenB）を交換する。
            スワップ(curA, curB);
        }
        // 長さの差を求める
intギャップ = lenA - lenB;
        // curA と curB を同じ開始点にします（終了位置は揃えます）
        while (ギャップ--) {  
            curA = curA->次へ;
        }
        // curA と curB を走査し、同じであれば直接戻ります
        (curA != NULL ) の場合 {
            もしcurA == curBの場合{
 curAを返します。
            }
            curA = curA->次へ;
            curB = curB->次へ;
        }
戻る  NULL ;
    }
 };

時間の計算量:
空間の複雑さ:

その他の言語

ジャワ

パブリッククラスソリューション{
パブリックListNode getIntersectionNode(ListNode headA、ListNode headB) {
        リストノード curA = headA;
        リストノード curB = headB;
整数lenA = 0、lenB = 0;
        while (curA != null ) { // リンクリストAの長さを見つける
            lenA++;
            curA = curA.next ;
        }
        while (curB != null ) { // リンクリストBの長さを見つける
            lenB++;
            curB = curB.next ;
        }
        curA = ヘッドA;
        カーソルB = ヘッドB;
        // curA を最長リンクリストの先頭とし、lenA をその長さとする
        （長さB＞長さA）の場合{
            //1. lenA、lenBを入れ替えます。
 int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap(curA, curB);
            リストノード tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 長さの差を求める
intギャップ = lenA - lenB;
        // curA と curB を同じ開始点にします（終了位置は揃えます）
        while (ギャップ--> 0) {  
            curA = curA.next ;
        }
        // curA と curB を走査し、同じであれば直接戻ります
        (curA != null ) の場合 {
            もしcurA == curBの場合{
 curAを返します。
            }
            curA = curA.next ;
            curB = curB.next ;
        }
戻る ヌル;
    } 
 
 }

パイソン

クラスソリューション:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
 「」 「 」
        速度の法則によれば、より速く歩く人はより遅く歩く人に必ず追いつくでしょう。
        この問題では、いくつかのリンク リストは短く、1 つのリンクを歩き終えた後、別のリンク リストを歩きます。これは、より速く移動するポインタとして理解できます。 
 
        次に、リンクされたリストの 1 つが完了したら、もう一方のリンクされたリストに進みます。交差点があれば、最終的には同じになる
        ロケーションエンカウンター
「」 「 」
        cur_a, cur_b = headA, headB # a と b の代わりに 2 つのポインタを使用します
 
 
        cur_a != cur_b の場合:
            cur_a = cur_a.next if cur_a else headB # a が終了したら b に切り替える
            cur_b = cur_b.next if cur_b else headA # 同様に、bが終了したらaに切り替えます
 
 cur_aを返す

行く

getIntersectionNode関数(headA, headB *ListNode) *ListNode {
    curA := headA
    カーソルB := ヘッドB
    長さA、長さB:=0、0
    // AとBの長さを求める
curA != nil {の場合
        curA = curA.次へ 
        lenA++
    }
 curB != nil の場合
        curB = curB.次へ 
        長さB++
    }
    var ステップint  
    var 高速、低速 *ListNode
    // 長さの差を要求し、長い方のリンクリストを先にします
    lenA > lenBの場合{
        ステップ = lenA - lenB
        速い、遅い = headA、headB
    }それ以外{
        ステップ = lenB - lenA
        速い、遅い = headB、headA
    }
 i:=0の場合; i < ステップ; i++ {
        速い = 速い。次へ 
    }
    // 2つのリンクリストを走査し、同じものを見つけたら走査から抜け出す
速い!= 遅い {
        速い = 速い。次へ 
        遅い = 遅い。次へ 
    }
早く戻る
}

ジャバスクリプト

var getListLen =関数(head) {
    len = 0、cur = headとします。
    while(cur) {
       長さ++;
       cur = cur.next ;
    }
長さを返します。
 }
 var getIntersectionNode =関数(headA, headB) {
    curA = headA、curB = headB とします。
        lenA = getListLen(headA)、
        lenB = getListLen(headB);
    lenA < lenB の場合
        [curA, curB] = [curB, curA];
        [lenA, lenB] = [lenB, lenA];
    }
    i = lenA - lenB とします。
    i -- > 0 の間 
        curA = curA.next  
    }
    curA && curA !== curB の場合
        curA = curA.next ;
        curB = curB.next ;
    }
 curAを返します。
 };