データ構造とアルゴリズム復習-02-チェーンテーブル

本文は私のGithubブログに先発します本文はデータ構造とアルゴリズムの復習の第2編の博文で、復習します

チェーンテーブルの概念

一般的なチェーンテーブルタイプと設計取捨

チェーンテーブルの反転動作

チェーンテーブルの概念
チェーンテーブルは次のように定義できます.

空

には、2つのプロパティを持つノードがあります.

val,本ノードの値

next、別のチェーンテーブル

まず,この定義は単一チェーンテーブルの定義であるが,双方向チェーンテーブルも同様である.
次に、この定義から、チェーンテーブルは再帰的に定義できることがわかります.
一般的なチェーンテーブルのタイプと設計の取捨選択
一般的なチェーンテーブルのタイプは

単鎖表

双方向チェーンテーブル

設計取捨選択とは主に以下のことを考慮する.

単一チェーンテーブルと双方向チェーンテーブルのどちらを選択しますか?

衛士ノード(sentinel node)は必要ですか?

シングルチェーンテーブルと双方向チェーンテーブル
双方向チェーンテーブルと単一チェーンテーブルの違いは

単一チェーンテーブル各ノードは、追加のチェーンテーブル(すなわち、後続要素)

を指すnextが1つしかない.

デュアルチェーンテーブル各ノードには、追加のチェーンテーブル(すなわち、前駆体および後続)

を指す2つの属性がある.
双方向チェーンテーブルの使用がより柔軟になります
選択方法
単一チェーンテーブルと二重チェーンテーブルの選択については、主に2つの点を考慮します.

空間、ダブルチェーンテーブルは1つの属性が多いため、消費空間はもっと

多い.

時間、ここでは

前駆ノードにアクセスする必要がある場合は、

デュアルチェーンテーブル

アクセスが必要な前駆ノードが固定されている場合、例えば、固定が前のノードまたは前の2つのノードである場合

は、追加のノードポインタを直接使用して

を記憶することができる.



衛士ノードが必要かどうか
衛士ノードとは
任意のチェーンテーブルに対して、チェーンテーブルが0ノードのチェーンテーブルではないように、不要なノードを追加します.
ガーディアンノードが必要かどうかは主に個人の使用習慣にかかっています

衛士ノードを使用すると、空のポインタの問題をある程度回避できます.

結局チェーンテーブルには必ずノード

がある.

しかし、1つのノードの空間消費が多くなり、プログラミングロジックと無衛士ノードのプログラミングロジックが異なる(くだらない話、もちろん異なる)

チェーンテーブルの反転操作
チェーンメーターの試験が一番多いのは反転です(淡々として単鎖時計の速い列がありますが、それはソートの時まで残しておいてもいいです)
チェーンテーブルの反転には2つの実装があります.

サイクル

を実現

再帰実装

実は論理が少し煩わしくて、本当にコードを暗記することができません
チェーンテーブルの反転をループで実現
次のコードの鍵は、ループの不変式にあります.
サイクルが開始されるたびに、headはまだ反転していないチェーンヘッダーを指し、prevは反転したチェーンヘッダーを指す.

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, next = null;
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

チェーンテーブルの反転を再帰的に実現
次のコードの鍵は、関数宣言にあります.reverseList(headA, headB)はheadAのチェーンテーブルを反転させ、headBのチェーンテーブルを反転headAのチェーンテーブルに接合した後

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverseList(head, null);
    }

    private ListNode reverseList(ListNode headA, ListNode headB) {
        if (headA == null) {
            return headB;
        }
        ListNode next = headA.next;
        headA.next = headB;
        return reverseList(next, headA);
    }
}