久々にアルゴリズムを日本語で解説してみました。
実はleetcodeアルゴリズムの問題はぽつぽつやっています。
個人的な感想は少し時間をかければ、大体理解できると思います。
少しくどく見えますかもしれませんが、わかりやすさを求めながら、
私の日本語のアウトプット練習もやっていきたい所存です。
本文：206問題リンク
edit1: 再帰方法のトレース表を更新しました。
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
複数Node持っている場合は全てのNodeの順番を反転しないといけません。
再帰方法はよりエレガントだと言われてます一方、
走査方法は理解しやすいです。
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;
}
再帰方法のトレース表
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;
}
走査方法のトレース表
