どうやって再帰的および非再帰的な方法で一方向チェーンを反転させるか？

問題：一方向チェーンを一つください。最初から最後まで逆転します。例えば、a->b->c->dは逆にd->c->b->aである。
解析：各nodeの構造を仮定すると、

class Node {
 char value;
 Node next;
}

はチェーンテーブルを反転させる際に、nodeの「next」の値を更新する必要がありますが、nextの値を更新する前に、nextの値を保存しなければなりません。したがって、私たちは2つのポインタがそれぞれ前のノードと後のノードに向けられ、現在のノード「next」値の更新が完了するたびに、最後のノードに到達するまで、2つのノードを下に移動する必要があります。コードは以下の通りです。

public Node reverse(Node current) {
 //initialization
 Node previousNode = null;
 Node nextNode = null;

 while (current != null) {
  //save the next node
  nextNode = current.next;
  //update the value of "next"
  current.next = previousNode;
  //shift the pointers
  previousNode = current;
  current = nextNode;   
 }
 return previousNode;
}

上のコードは非再帰的な方法を使用しています。この問題は再帰的な方法で解決できます。コードは以下の通りです。

public Node reverse(Node current)
 {
     if (current == null || current.next == null) return current;
     Node nextNode = current.next;
     current.next = null;
     Node reverseRest = reverse(nextNode);
     nextNode.next = current;
     return reverseRest;
 }

の再帰方法は実は非常に巧妙で、それは再帰的にチェーンの端まで行って、それから各nodeのnext値を更新します。上のコードの中で、reverseRestの値は変更されていません。チェーンの最後のnodeです。だから、反転したら、新しいチェーンのheadが得られます。