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

[[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を返します。
 };