剣指offer(3)——最後からチェーンを印刷します.

2342 ワード

テーマの説明
チェーンを入力して、最後の端からチェーンテーブルの順にArayListを返します.
問題を一つ解く
問題を読み終わったら、最後の端から順に印刷するのが目的です.つまり逆順印刷に相当します.逆順印刷はデータ構造を連想させやすいです.その答えは出てきます.多くない無駄なコードは以下の通りです.

public ArrayList printListFromTailToHead(ListNode listNode) {
        Stack stack = new Stack<>();
        ArrayList arrayList = new ArrayList<>();
        while (listNode != null) {
            stack.add(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()) {
            arrayList.add(stack.pop());
        }
        return arrayList;
    }

問題2
逆順で印刷するなら、まずチェーンを反転させてからやり直します.チェーンとツリーは彼のデータ構造特性のため、通常は再帰的に操作できます.再帰的に反転を実現します.
多くの仲間が接触を始めたら再帰的になるかもしれません.熟れていてうまくいくというのは、再帰的にも彼のコツがあります.コツを把握して、大量の練習に協力すれば、後で再帰的に解決されます.
再帰的にマクロを重んじて、くれぐれも思い詰めてはいけなくて、さもなくばきわめてその中に陥って抜き出すことができないかもしれなくて、いわゆる大局観はこのようにハッとします.次は三歩に戻る.

終了条件を見つける

戻り値を見つける

このステップは何をしましたか?
反転関数:

 public static ListNode reserve(ListNode listNode) {
        if (listNode==null||listNode.next == null) {
            return listNode;
        }
        ListNode newHead = reserve(listNode.next);
        listNode.next.next = listNode;
        listNode.next = null;
        return newHead;
    }

終了条件:チェーンを反転させるので、反転された新しいチェーンの先頭に戻るだけでいいです.チェーンの最後のnextが空の時に戻ってもいいです.現在のチェーンテーブルが空かどうかは、ロバスト性を高めるため、つまり、入ってきたチェーン自体が空です.

戻り値:新しいチェーンヘッダを返してもいいです.

このステップは何をしましたか?例えば、この再帰関数はreverse()関数と呼ばれ、このreverse(head.next)を呼び出した後、head.nextからのチェーンは全部反転されました.プログラムが具体的にどのように実現されているかは分かりません.呼び出しだけでチェーンが反転します.まず大局から出発して、headを反転させたチェーンテーブルの後に貼り付けます.

このようにして、私達は構想によってコードを書くことができます.完全なコードは以下の通りです.

public ArrayList printListFromTailToHead(ListNode listNode) {
        ArrayList list = new ArrayList<>();
        ListNode head = reserve(listNode);
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        return list;
    }

    public static ListNode reserve(ListNode listNode) {
        if (listNode==null||listNode.next == null) {
            return listNode;
        }
        ListNode newHead = reserve(listNode.next);
        listNode.next.next = listNode;
        listNode.next = null;
        return newHead;
    }

uva 11992区間は線分樹を修正します.