単方向リストとその反転

単方向リストは、任意のアドレスのストレージユニットのセットを使用して線形リスト内のデータ要素を格納する、リンクされたアクセスのデータ構造です。リスト内のデータはノードとして表され、各ノードは要素とポインタで構成され、要素はデータを格納するストレージユニットであり、ポインタは各ノードを接続するアドレスデータです。本記事では、単方向リストとは何か、単方向リストの反転について紹介します。主な内容は以下の通りです：

単方向リストとは
単方向リストの反転を遍歴する
単方向リストの反転を再帰的に行う

単方向リストとは#

単方向リストの各ノードには、2 つのストレージ領域があります。一つは対応するノードのデータを格納し、もう一つはそのノードの次のノードのアドレスを格納します。これを後続ポインタ（next）と呼ぶことができます。単方向リストの図は以下の通りです：

ヘッドノード：リストの最初のノードで、リストの基準アドレスを記録するために使用されます。
テイルノード：リストの最後のノードで、その後続ポインタ（next）は空のアドレスを指します。

単方向リストの反転を遍歴する#

一つ覚えておいてほしいのは、リストの反転は実際にはリスト内のポインタを反対方向に指すようにすることです。単方向リストが A->B->C->D の場合、反転後は D->C->B->A になります。遍歴方式で単方向リストを反転するのは、各ノードを順次反転させることです。

順次反転する際、A ノードの next ポインタは null を指し、次に B ノードの next ポインタは A ノードを指します。最終的に単方向リストの反転が完了します。遍歴反転単方向リストの図は以下の通りです：

具体的なコードは以下の通りです：

/**
 * リストの反転（遍歴）
 *
 * @param head
 * @return
 */
public Node<T> reverse(Node<T> head) {

    /**
     * 思考：リストA->B->C->Dを反転するには、ヘッドノードであるAノードをnullに指し、BノードをAノードに指すようにします。これを繰り返します。
     *      反転中はリストの切断に注意し、切断されたリストを失わないようにします。
     *
     * リストの反転は実際にはリスト内のポインタを反対方向に指すことです。
     */

    Node<T> tempNode = null;
    while (head != null) {
        // 反転によって切断されたリストを記録
        Node<T> nextNode = head.next;
        // リストの反転
        head.next = tempNode;
        // tempNodeポインタを移動
        tempNode = head;
        // headポインタを移動
        head = nextNode;
    }
    return tempNode;
}

単方向リストの反転を再帰的に行う#

単方向リストを反転するもう一つの方法は再帰です。核心的な考え方は、大きな問題を小さな問題に変えることです。一般的に言えば、複数のノードの単方向リストはさらに小さな単方向リストに分けることができます。例えば、1 ノードの単方向リストはそれ自体であり、2 ノードの単方向リスト A->B->null の場合、反転時には隣接ノードのポインタを逆向きにすればよいのです。つまり、ノード B の next ポインタを A に指し、A の next ポインタはまだ B を指しているので、A の next ポインタを null に指す必要があります。コードは以下のように表されます：

// リストA->B->nullを反転
B.next = A;
A.next = null;

再帰方式で単方向リストを反転する図は以下の通りです：

具体的なコードは以下の通りです：

/**
 * リストの反転（再帰）
 *
 * @param head
 * @return
 */
public Node<T> reverse(Node<T> head) {

    /**
     * 思考：再帰の考え方を使用して解決します。
     *
     * リストの反転では、常に2つの隣接ノードのポインタを逆向きにすることを忘れないでください。
     */

    if (head == null || head.next == null) {
        return head;
    }
    
    // newNodeは最終的に反転されたヘッドノードです
    Node<T> newNode = reverse1(head.next);
    head.next.next = head;
    head.next = null;
    return newNode;
}

上記では単方向リストとその反転の 2 つの方法について紹介しました。誤りがあればご指摘ください。