一般的なチェーンテーブル操作-単一チェーンテーブル反転(JAVA実装)

テクニカル面接では、一般的な質問など、単一チェーンテーブルの操作がよく聞かれます.

単鎖表反転

チェーンテーブルにおけるリングの検出

2 2つの順序付きテーブルのマージ

チェーンテーブルの最後からn番目のノード

を削除する.

チェーンテーブルの中間ノード

を求める
次の文章では、これらの操作の実装アルゴリズムについていくつかまとめました.具体的な実装のプログラミング言語はJavaです.
今日の第1編では,まず単一チェーンテーブルの反転を実現する方法について述べる.
実現構想.
最初のステップは、最初のノードからチェーンテーブルを巡り、最後のノードを見つけます.
第2のステップでは、エンドノードから、各ノードのnext参照をエンドノードまで逆方向に変更します.
ステップ3では、ヘッダノードのnext参照をnullに変更します.
インプリメンテーションコード
ノード構造を定義します.

/**
 *   ADT
 * 
 * @author wangtao
 * @param 
 */
public class LinkADT<T> {

    /**
     *      
     * 
     * @author wangtao
     * @param 
     */
    private static class SingleNode<T> {
        public SingleNode<T> next;
        public T data;

        public SingleNode(T data) {
            this.data = data;
        }

        public T getNextNodeData() {
            return next != null ? next.data : null;
        }
    }
}

第1の実現案は,再帰的な考え方を用い,分かりやすいが簡潔ではない.

    /**
     *       version1
     * 
     * @param node
     *                
     * @param pre
     *                 
     * @return
     */
    public static SingleNode reverseV1(SingleNode node, SingleNode pre) {

        if (node == null) {
            return node;
        } else {
            //        
            SingleNode headNode;

            // next  ，      
            if (node.next == null) {
                //   next  
                node.next = pre;
                //          
                headNode = node;
            } else {
                //     ，    
                headNode = reverseV1(node.next, node);
                //
                node.next = pre;
            }

            return headNode;
        }
    }

検証結果.

    /**
     *       
     * 
     * @param node
     */
    public static void printLink(SingleNode node) {
        System.out.println("current node data:" + node.data + ", next node data:" + node.getNextNodeData());

        if (node.next != null) {
            printLink(node.next);
        } else {
            System.out.println("-------------");
        }
    }

    public static void main(String[] args) {
        SingleNode<Integer> s1 = new SingleNode<>(1);
        SingleNode<Integer> s2 = new SingleNode<>(2);
        SingleNode<Integer> s3 = new SingleNode<>(3);
        SingleNode<Integer> s4 = new SingleNode<>(4);
        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        
        printLink(s1);
        SingleNode<Integer> firstNode = reverseV1(s1, null);
        printLink(firstNode);
    }

印刷の結果、チェーンテーブルが正しく反転します.

current node data:1, next node data:2
current node data:2, next node data:3
current node data:3, next node data:4
current node data:4, next node data:null
-------------
current node data:4, next node data:3
current node data:3, next node data:2
current node data:2, next node data:1
current node data:1, next node data:null
-------------

どうして前の案が簡潔ではないと言ったのですか.パラメータには、現在のノードの前のノード、例えば次のコードがあるからです.

    SingleNode<Integer> firstNode = reverseV1(s1, null);

次に、より簡潔な第2の実装スキームを見てみましょう.

    /**
     *       version2
     * 
     * @param node
     * @return
     */
    public static SingleNode reverseV2(SingleNode node) {
        if (node == null || node.next == null) {
            return node;
        } else {
            SingleNode headNode = reverseV2(node.next);
            node.next.next = node;
            node.next = null;
            return headNode;
        }
    }

次の行のコードに重点を置き、次のノードのnext参照を現在のノードに変更します.一見バグがあると思い、よく分析してみると問題ないと思いますが、分からないと思ったら、一度ブレークポイントをつけることをお勧めします.

node.next.next = node; 

まとめ
シングルチェーンテーブルの反転は簡単に見えますが、準備ができていない場合は正しく書くのも容易ではありません.時間をかけて、1、2時間かけてコードを書いてくれれば、みんながマスターできると信じています.
完全なコード:https://github.com/wanf425/Algorithm/blob/master/src/com/wt/adt/LinkADT.java
次の文章では、チェーンテーブルのループの検出をどのように実現するかをまとめ続けます.
ブログアドレス
https://www.taowong.com/blog/2018/10/14/data-strutctures-and-algorithm-01.html