面接ベストチェーン問題集錦

10589 ワード

チェーンテーブルの問題は面接の過程でよく聞かれる一部で、プログラミングの基礎をよく調べています.最近LeetCodeのチェーンテーブル部分の面接問題をチェックして、代表的なチェーンテーブルの問題をまとめました.
この文書ではJava言語を使用しています.次に、使用するチェーンテーブルノードの定義を示します.

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

1.チェーンテーブルノードをO(1)時間で削除する
Leetcode 237. Delete Node in a Linked List
タイトル説明:指定された単一チェーンテーブルで削除する必要があるノード(エンドノードではない)は、O(1)時間で削除されます.
分析:本題は『プログラミングの美』の「無頭単鎖表からノードを削除する」と似ている.主なアイデアは「タヌキ交換太子」で、削除するノードを次のノードデータで上書きし、次のノードを削除することです.しかし,ノードがエンドノードである場合,この方法は通用しない.
コードは次のとおりです.

//   O(1)              
public void deleteNode(ListNode node) {
    //     ，      
    if (null == node || null == node.next) {
        return;
    }
    node.val = node.next.val;
    node.next = node.next.next;
}

2.逆転単鎖表
LeetCode 206. Reverse Linked List
タイトル説明:単一チェーンテーブルの逆順序反転後のチェーンテーブルを出力します.
分析:非再帰アルゴリズムは簡単で、3つの一時ポインタprev、cur、nextでチェーンテーブルを1回循環すればいい.再帰アルゴリズムは,まず次のノードを逆転し,次に現在のノードを逆転する.
次の2つのアルゴリズムのコードを示します.

//      ，    
public ListNode reverseByLoop(ListNode head) {
    if (null == head || null == head.next) {
        return head;
    }
    ListNode prev = null;
    ListNode next = null;
    //   head    cur   
    while (null != head) {
        next = head.next;

        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

//      ，    
public ListNode reverseByRecursion(ListNode head) {
    //          ，          
    if (null == head || null == head.next) {
        return head;
    }

    ListNode newHead = reverseByRecursion(head.next);

    head.next.next = head;
    head.next = null;

    return newHead;
}

3.単一チェーンテーブルの最後からn番目のノードを削除する
LeetCode 19. Remove Nth Node From End of List
タイトル説明:単一チェーンテーブルの最後からn番目のノードを削除し、1<=n<=lengthで、できるだけ1回の遍歴で完了します.
解析:問題を見たときの第一の考え方は,まず単一チェーンテーブルの長さlengthを1回計算し,次いで2回目にlength−n+1ノードを削除することであるが,これは2回の遍歴が必要である.正常にn番目のノードを削除するには1回だけ遍歴すればいいのですが、どのようにして最後からn番目のノードを1回だけ遍歴すればいいのでしょうか.2つのポインタp 1,p 2を設定することができ、まずp 1とp 2がheadを指し、p 2がn番目のノードに移動し、p 1とp 2が同時に後方に移動し、p 2が末尾に移動すると、p 1はちょうど逆数のn番目のノードを指す.最後に最後のn番目のノードを削除するので、最後のn+1番目のノードを見つけることができ、ノードの削除が容易になります.
コードは次のとおりです.

//     ，         n    
public ListNode removeNthFromEnd(ListNode head, int n) {
    if (null == head) {
        return head;
    }
    ListNode p1 = head;
    ListNode p2 = head;
    // 1. p2      n + 1    
    for (int i = 0; i < n; i ++>) {
        p2 = p2.next;
    }
    // n ==      ，p2     n + 1     ，    n         
    if (null == p2) {
        p1 = head.next;
        return p1;
    }
    // p1   p2       ，   p2      
    while (null != p2.next) {
        p1 = p1.next;
        p2 = p2.next;
    }
    //    p1       n + 1    ，         
    p1.next = p1.next.next;
    return head;
}

4.単一チェーンテーブルの中間ノードを求める
タイトル説明:単一チェーンテーブルの中間ノードを求めて、もしチェーンテーブルの長さが偶数ならば、中間の2つのノードのいずれかを返して、奇数ならば、中間ノードを返します.
分析:この問題の構想は第3題の「単鎖表の最後からn番目のノードを削除する」とよく似ている.チェーンテーブルの花を1回しか回らないように要求された場合も、2つのポインタで完成します.2つのポインタは、先頭ノードから始まり、遅いポインタは1歩後ろに移動し、速いポインタは2歩後ろに移動し、速いポインタが末尾ノードに移動するまで、遅いポインタは中間ノードに移動します.

//     ，          
public ListNode findMiddleNode(ListNode head) {
    if (null == head) {
        return;
    }
    ListNode slow = head;
    ListNode fast = head;
    //                 ，            ，          
    //while(null != fast.next && null != fast.next.next)
    while (null != fast && null != fast.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

5.単一チェーンテーブルにループがあるかどうかを判断する
LeetCode 141. Linked List Cycle
テーマの説明:1つの単鎖の表が環があるかどうかを判断します
解析:やはり高速ポインタで解決します.2つのポインタは最初からノードで始まり、遅いポインタは毎回1歩後ろに移動し、高速ポインタは毎回2歩後ろに移動します.リングが存在する場合、2つのポインタは必ずリング内で出会います.
コードは次のとおりです.

//          
public boolean hasCycle(ListNode head) {
    if (null == head) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (null != fast.next && null != fast.next.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}

6.単一チェーンテーブルにループ拡張があるかどうか:ループのエントリポイントを見つける
LeetCode 142. Linked List Cycle II
タイトル説明:単鎖表に環があるかどうかを判断して、もしあるならば、環の入り口の点を探し当てます
分析:上の問題から分かるように、p 2は毎回2歩、p 1は毎回1歩の方式で歩いて、p 2とp 1が重なることを発見して、一方向チェーンテーブルにループがあることを確定しました.次に、p 2をチェーンテーブルの頭に戻して、再び歩いて、毎回のステップ長は2を歩いたのではなく、1を歩いて、p 1とp 2が再び出会ったとき、ループの入り口点にあります.
始点からリング入口までの距離尾a,p 1とp 2が初めて出会った交差点Mとリング入口との距離をb,リングの周長をLとし,p 1とp 2が初めて出会ったとき,p 1がnステップを歩んだと仮定する.ここで、p 1とp 2が初めて出会ったとき、p 1がリング内を歩いた歩数はbであり、p 1がリング入口まで歩いたとき、p 2はリング内にいたので、このときp 2がリング入口まで歩いた歩数がcであると仮定すると、p 1がc歩p 2を歩いてちょうどp 1と出会って、cp 1歩く経路:a + b = np 2歩く経路:a + b + k * L = 2nこのときp 2がp 1より多くkループを歩いたとすると、k>=1
以上の2つの式からk * L = n = a + bが得られるが、交差点Mからp 1がa(a=k*L-b)ステップを歩むことは、kループを歩いたことに相当し、bステップを後退し、ループ入口から交差点までの距離がちょうどbであることに注意して、p 1がaステップを歩くとループ入口に到達する.そしてp 2は最初からaを歩くと環入口に着き、p 1と出会う.
そして、後のステップでは、p 1とp 2の前のaステップの経路が異なり、再び出会うときは必ずリングの入口点にある.
コードは次のとおりです.

//        
public ListNode findLoopPort(ListNode head) {
    if (null == head) {
        return null;
    }
    ListNode p1 = head;
    ListNode p2 = head;
    boolean hasCycle = false;
    // 1.       
    while (null != p2.next && null != p2.next.next) {
        p1 = p1.next;
        p2 = p2.next.next;
        if (p1 == p2) {
            hasCycle = true;
            break;
        }
    }
    if (!hasCycle) {
        return null;
    }

    // p2      ，     1
    p2 = head;
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

7.2つの無環単鎖表が交差しているかどうかを判断する
テーマ説明:2つの無環単鎖表を与える

A:       a1 → a2
                 ↘
                    c1 → c2 → c3 → null
                 ↗            
B:  b1 → b2 → b3

AとBが交わっているかどうかを判断する.
分析:
1.最も直接的な方法は、Aチェーンテーブルの各ノードがBチェーンテーブルにあるかどうかを判断することであるが、この方法の時間的複雑度はO(Length(A)*Length(B))である.
2.リングに変換する問題.BチェーンテーブルをAチェーンテーブルの後ろに接続し、得られたチェーンテーブルにリングがあれば、2つのチェーンテーブルが交差していることを説明する.ループがあるかどうかを判断するには、前に議論した速いポインタを使用することができますが、ここではもっと簡単な方法があります.BチェーンテーブルとAチェーンテーブルが交差している場合、BチェーンテーブルをAチェーンテーブルの後ろに接続すると、Bチェーンテーブルのすべてのノードがリング内にあるので、この場合はBチェーンテーブルを遍歴して、起点に戻るかどうかを見て、交差するかどうかを判断することができます.この方法は,まずAチェーンテーブルを1回遍歴し,テールノードを見つけ,次にBチェーンテーブルを1回遍歴し,リングが形成されているか否かを判断し,時間的複雑度はO(Length(A)+Length(B))である.
3.リングに変換する問題に加えて、「2つのチェーンテーブルがあるノードに交差している場合、その後のノードが共有されている」という特徴を利用することもできます.2つのチェーンテーブルが交差している場合、最後のノードは必ず共有されます.したがって、Aチェーンテーブルを巡回し、テールノードを記憶した後、Bチェーンテーブルを巡回し、2つのチェーンテーブルのテールノードを比較し、同じであれば交差し、異なるであれば交差しない別の解法が得られる.時間的複雑度はO(Length(A)+Length(B)),空間的複雑度はO(1)であり,解法2よりも考え方が簡単である.
解法3のコードは次のとおりです.

//              
public boolean isIntersect(ListNode headA, ListNode headB) {
    if (null == headA || null == headB) {
        return false;
    }
    if (headA == headB) {
        return true;
    }
    while (null != headA.next) {
        headA = headA.next;
    }
    while (null != headB.next) {
        headB = headB.next;
    }
    return headA == headB;
}

8.2つのチェーンテーブルの交差拡張:2つのループ付き単一チェーンテーブルが交差しているかどうかを判断する
上の問題は無環チェーンテーブルに対してですが、チェーンテーブルにリングがあれば?
解析:2つのループが単一チェーンテーブルで交差している場合、それらは必ず1つのループを共有します.したがって、2つのチェーンテーブルのうちリング内にある2つのノードを、前のスナップポインタで見つけることができ、交差すると、2つのノードが1つのリング内にある場合、1つのノードを移動し、1つのループ内で他のノードと出会うことができるに違いない.
コードは次のとおりです.

//              
public boolean isisIntersectWithLoop(ListNode headA, ListNode headB) {
    if (null == headA || null == headB) {
        return false;
    }
    if (headA == headB) {
        return true;
    }
    headA = hasCycle(headA);
    headB = hasCycle(headB);
    //    ，   
    if (null == headA || headB) {
        return false;
    }

    ListNode p = headB.next;
    // p        ，    headA   
    while (p != headB) {
        if (p == headA) {
            return true;
        }
        p = p.next;
    }
    return false;
}

//          ，          
public ListNode hasCycle(ListNode head) {
    if (null == head) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (null != fast.next && null != fast.next.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            return slow;
        }
    }
    return null;
}

9.2つのチェーンテーブルの交差拡張:2つの無環単鎖テーブルの第1の交差点を求める
LeetCode 160. Intersection of Two Linked Lists
トピックの説明:2つの無ループ単一チェーンテーブルの最初の交差点を見つけ、交差しないと空に戻ると、線形時間の複雑さと定数空間の複雑さで完了する必要があります.
分析:
次の位置合わせ:ポインタがチェーンテーブルの末尾までの距離が同じであることを示します.

ループがあるかどうかを先に判断し、最初の交差点を求める方式に分けます.AチェーンテーブルとBチェーンテーブルをそれぞれ巡回し,それらの最後のノードが交差しているか否かを判断する.次に,整列の考え方を用いて,2つのチェーンテーブルの長さ(これは以前の遍歴で行うことができる)を計算し,それぞれp 1とp 2で2つのチェーンテーブルのヘッダを指し,その後,長いチェーンテーブルのp 1(p 1と仮定)を後方に移動するLB - LAノード.こうしてp 1とp 2が整列し、p 1とp 2を同時に後ろに移動してp1 == p2に至るまで、出会った点が最初のノードである.

解法1では整列のためにチェーンテーブルの長さを計算する必要がありますが、チェーンテーブルの長さを計算しなくてもいい方法はありますか?AチェーンテーブルとBチェーンテーブルの長さがLAとLBであると仮定し、LB>=LAであると仮定し、2つのポインタp 1とp 2はそれぞれAチェーンテーブルとBチェーンテーブルのヘッダノードを指す.同時に後ろに移動し、p 1がAチェーンテーブルの末尾を移動すると、p 2のBチェーンテーブルの末尾からの距離はLB - LAとなり、この場合には長さ差が得られていることがわかりますが、この長さ差で位置合わせするにはどうすればいいのでしょうか.このときp 1をBチェーンテーブルの頭部に移動し、2つのポインタが移動し続け、p 2がBチェーンテーブルの末尾に移動すると、p 1がちょうど移動したLB - LAステップ.このとき、p 2をAチェーンテーブルの頭部に移動し、p 1とp 2が整列した後、p1 == p2まで移動を継続する.2つのチェーンテーブルが交差しない場合、p 1とp 2の移動は同時に末尾まで移動して空を指し、交差すると、最初が等しいときが最初の交差点になります.この方法の時間的複雑さはO(2＊(Length(B)))であり,長さの長いチェーンテーブルを最大2回遍歴しなければならない.

2のコードは以下の通りです.

//                
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (null == headA || null == headB) {
        return null;
    }
    if (headA == headB) {
        return headA;
    }

    ListNode p1 = headA;
    ListNode p2 = headB;
    while (p1 != p2) {
        //                   
        //   p1   p2          ，     ：
        // （1）      ，p1 == p2         
        // （2）       ，p1   p2        ，p1 = p2 = null，      
        p1 = (null == p1) ? headB : p1.next;
        p2 = (null == p2) ? headA : p2.next;
    }
    return p1;
}

10.まとめ
振り返ってみると、上記のチェーンテーブルの問題は主に「タヌキが太子を交換する」「位置合わせ」「2つのポインタ」という方法で効率を高めていることがわかります.このうち2つのポインタを用いて効率を提供する方法はよく用いられ,チェーンテーブルの問題に遭遇したときにこのような考え方を多く考慮することができる.これらの典型的なチェーンテーブルの問題を覚えておくことをお勧めします.これからは似たような問題をよく知っている問題に変えて解決することができます.
参考記事:

面接選考:チェーン問題集錦

チェーンテーブルの削除チェーンテーブルa/bにおけるノード

組織機構コードと統一社会信用コード検証規則およびjava検証ツールクラス