leetcode問題番号206チェーンテーブルを反転

タイトルの詳細を表示するには、ここをクリックしてください.
タイトル
単一チェーンテーブルを反転します.
例:
入力:1->2->3->4->5->NULL出力:5->4->3->2->1->NULL
問題を解く構想.
単一チェーンテーブルを反転することは、チェーンテーブルで一般的な操作とみなされ、ループと再帰の2つの方法で解決されます.

サイクルまずサイクルの考え方を話します.実は2つのチェーンテーブルがあり、1つは反転が必要なチェーンテーブル(以下(チェーンテーブルs)と呼ばれ、1つはすでに反転されたチェーンテーブル(以下チェーンテーブルrと呼ぶ)であり、最初はチェーンテーブルrが空のチェーンテーブルであり、チェーンテーブルsを遍歴し、1つのノードを遍歴するとチェーンテーブルsのヘッダノードを1つのノードに後方に移動し、チェーンテーブルsのヘッダノードが空になり、空にされたヘッダノードは、チェーンテーブルrのヘッダノードとしてチェーンテーブルrに挿入され、チェーンテーブルsがエンドノードに遍歴するまで繰り返し操作され、コードは以下の通りである.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode reverseHead = null, posHead = null;
        ListNode curr = head;
        while(curr != null) {
            posHead = curr.next;
            curr.next = reverseHead;
            reverseHead = curr;
            curr = posHead;

        }
        return reverseHead;
    }
}

再帰再帰の鍵は、まず再帰式を見つけることであり、チェーン全体の反転をチェーン上の各ノードの反転に分解することができるが、ノードの反転は、実際には、後のノードを指すことから後のノードを指すことに変換され、式に変換することは

である.
reverseは、反転関数nextNodeが反転するノードを示す次のノードnextNodePointが次のノードを示す後続ポインタが反転するノードを指す
再帰式があれば,再帰式の定数値,すなわち再帰法の終了条件を見つける必要がある.反転した終了ノードはチェーンテーブルの末尾ノードであり,ノードの後続ポインタがNULLの場合に再帰を終了する.
ノードの後続ポインタが空の場合
再帰的な方式分析が終わり、コードは以下の通りです.

class Solution {
    public ListNode reverseList(ListNode node) {
        if(node == null || node.next == null) {
            return node;
        }

        ListNode reverseHead = reverseList(node.next);
        node.next.next = node;
        node.next = null;
        return reverseHead;
    }
}