Linked List反転の一般的な解き方

久々にアルゴリズムを日本語で解説してみました。
実はleetcodeアルゴリズムの問題はぽつぽつやっています。
個人的な感想は少し時間をかければ、大体理解できると思います。
少しくどく見えますかもしれませんが、わかりやすさを求めながら、
私の日本語のアウトプット練習もやっていきたい所存です。
本文：<a href="https://leetcode.com/problems/reverse-linked-list/description/">206問題リンク</a>

edit1: 再帰方法のトレース表を更新しました。

---
Example 1:

![01.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3589185/1c30dbbb-40ec-474f-a7e2-f4db2aa2ae54.jpeg)

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]


Example 2:

![02.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3589185/e1bafcd5-d4f6-455d-91d4-d44494ef23b1.jpeg)

Input: head = [1,2]
Output: [2,1]

Example 3:
Input: head = []
Output: []

複数Node持っている場合は全てのNodeの順番を反転しないといけません。

---

再帰方法はよりエレガントだと言われてます一方、
走査方法は理解しやすいです。
```Java:ReverseLinkedList.java 
/**
 * Definition for singly-linked list.
 * public class Node {
 *     int val;
 *     Node next;
 *     Node() {}
 *     Node(int val) { this.val = val; }
 *     Node(int val, Node next) { this.val = val; this.next = next; }
 * }
 */
 // 普通のアプローチは 1.再帰方法および 2.走査方法二つの解き方がある。
    // 1.再帰方法
    //   先ずは最後のnodeを見つける。
    // (1)新たなリストのhead nodeとして返しながら現在のnode次のnodeの「next」
    //    属性ポインタに、現在のnodeを割り当る。
    // (2)循環リスト(Looped List)を避けるために、現在のnodeの「next」
    //    属性ポインタをnullにしておき、一つ前のnodeが操作される際に再代入する。
    //    この二つの操作を繰り返し、元々1番のnodeの「next」はnullになる。
    public Node reverse(Node head) {
        // リストがnullの場合。若しくは1つnodeしか持っていない、
        // 又は最後から１番のnodeに辿り着いた場合。
        // head nodeをそのまま回転済みのリストの1番のnodeとして返す。
        if (head == null || head.next == null) {
            return head;
        }
        // 複数のnodeが持っている場合はNodeの反転操作が必要。
        // 現在操作されているnodeの次のnodeを新しく出来たリストの1番のnode
        // 見なして反転メソッドreverseに渡し、後ろの全てのnodeの処理が済んでいたら、
        // 現在のnodeを処理する。
        Node nextNode = head.next;
        // 新たなリストの１番のnode(newHead)は見つけてから、n-1回の処理を
        // 経っても一度変わったことはない(nはnodeの数)。
        // まるで水面を吹き通った風のように、水面（現在のnode）に何が起こっても
        // 関係ない、風(newHead)は目的地(メソッドreverseの呼び出し元)に辿り着く。
        Node newHead = reverse(nextNode);
        //　次のnodeでnextポインタに現在のnodeを割り当て、つまり新たなリストに
        // 最後から1番のnodeとして連結する。
        nextNode.next = head;
        // 現在のnodeのnextポインタをnullにする。新たなリストの最後から1番の
        // nextポインタはnullではないか。
        head.next = null;
        // 新たなリストが出来たため、1番のnodeを返す。
        return newHead;
    }
```
再帰方法のトレース表
![reverseListMethod1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3589185/b3dfd646-bdd3-4258-ae95-1214678bdc2f.png)


```Java:ReverseLinkedList.java 
    // 2.走査方法
    // 原始リストのnodeを新たなリストのhead nodeとして連結し、
    // 作り終わったら、元々最後から1番のnodeをhead nodeとして返す。
    public static Node reverse(Node node) {
        // 新たなリストに最後から1番のnodeのnextポインタにnull(node)を用意
        Node pre = null;
        // まだ原始リストに順番が回って来ないnodeをとりあえずnullで初期化しておく。
        Node nextNode = null;
        // 原始リスト最後から１番目のnodeに辿りついてない限り、
        // node反転の繰り返し作業を続ける。
        while (node != null) {
            // nextNodeに切り残した原始リストのhead nodeを割り当てる
            nextNode = node.next;
            //　現在のnodeを新たなリストのhead nodeとして、next属性ポインタに
            //  一つ前のnodeを割り当てる。
            node.next = pre;
            // 連結済みの現在のnodeを新たなリストの2番目のnodeにしておく。
            pre = node;
            // 次のnodeの連結作業に移す。
            node = nextNode;
        }
        // 原始リスト最後から1番目のnodeの次のnode
        //（現在のnode）がnullの場合,while文が終わり。
        // しかし原始リスト最後から1番目のnodeは既にpre変数に割り当てているため、
        // preを新たなリストhead nodeとして返す。
        return pre;
    }
```
走査方法のトレース表
![reverseListMethod2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3589185/fd10fe8e-5f5a-42f1-aec3-22f3d52c094e.png)