単方向リストは、リニアリストのデータ要素を格納するための一連のアドレス任意のストレージユニットを使用する、リンクされたアクセスデータ構造です。リスト内のデータは、ノードによって表され、各ノードは要素とポインタで構成されます。要素はデータを格納するストレージユニットであり、ポインタは各ノードを接続するアドレスデータです。この記事では、単方向リストとその反転について説明します。主な内容は以下の通りです：
- 単方向リストとは何か
- 単方向リストの反転のための反復処理
- 単方向リストの反転のための再帰処理
単方向リストとは何か#
単方向リストの各ノードには、2 つのストレージ領域があります。1 つは対応するノードのデータを格納し、もう 1 つはそのノードの次のノードのアドレスを格納します。これは後続ポインタ（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;
}
再帰的な単方向リストの反転#
2 番目の方法は、再帰を使用した反転です。核心的なアイデアは、大きな問題を小さな問題に分割することです。単方向リストの複数のノードはすべて、より小さな単方向リストにさらに分割できます。たとえば、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 つの方法について説明しました。誤りがあればご指摘ください。