リンクリスト: これは逆にしたい連結リストです。
逆リンクリストの後: 以下は、上記のリンクされたリストを逆にした後の結果になります。
上の図の例では、リンクされたリストを逆にすると、ヘッド ノードとテール ノードの位置が変わることがわかります。テール ノードになったヘッド ノードは、テール ノードになったため、ヌル ノードを指します。
アルゴリズムの手順
- メイン メソッドを作成し、いくつかの必要な変数を宣言します。
- 次に、リンク リストを作成できるメソッドを作成します。このメソッドは、リンクされたリストを作成するのに役立ちます。
- 次のステップは、リンクされたリストを逆にするメソッドを作成することです。このメソッドでは、リンクされたリスト全体を渡します。このメソッドは、リンクされたリストを逆にします。
- ここで、反転後に結果を表示する別の方法が必要です。
- 上記のすべてのメソッドをメイン メソッドに結合します。
逆連結リストを絵でわかりやすく説明します。それでは、例から始めましょう。
以下は、逆にしたいリンクされたリストです。
ステップ1 .緑色のノードはヘッド ノードで、起動時の最初のノードを指します。
ステップ2。 次のステップでは、ヘッダー ノードの横にヌル ポインターが表示されなくなるまで、リンク リスト全体をトラバースします。そのために、下の図に示すように、次のノードに一時的な名前を割り当てます。
ステップ 3。 「temporary」という名前の新しい参照ノードがあるため、null ポインターを取得しなくなるまで、リンクされたリスト全体をトラバースするのに役立ちます。そのため、ヘッダー ノードの次のリンクを null として設定できます。これは、リンクされたノードに影響しません。下の図のようにリストします。現在のノードの次のヌル ポインターは、前のノードと呼ばれます。
ステップ 4。 ここで、一時ノードを次のノードに移動し、現在のノードを前の一時ノードに移動します。これで、次のノードに移動しました。また、前のノードを null から現在のノードの前のノードだけに変更します。したがって、現在のノードのリンクを前のノードに設定できるように、一時ノードはヌル ポインターまでのすべてのトラバースを処理し、下の図に示すように前のノードを指しています。
したがって、同じ手順を実行すると、最後に逆リンク リストが得られます。
ステップ 5 .
ステップ6。
ステップ 7。
ステップ 8.
ステップ 9。
ステップ10。
ステップ11。
ステップ12。
ステップ13。
ステップ14。 このステップで、リンクされたリストが逆になりました。
リンクされたリストを逆にする C++ プログラム
#include使用して 名前空間 標準 ;
// ノードを作成するメソッド
構造体 ノード {
整数 価値 ;
ノード * nextNodePtr ;
} * ノードオブジェクト ;
空所 createLinkedList ( 整数 n ) ;
空所 逆リンクリスト ( ノード ** ノードオブジェクト ) ;
空所 画面 ( ) ;
整数 主要 ( ) {
整数 n,値,アイテム ;
カウト << '作成するノードの数 =>: ' ;
食べる >> n ;
createLinkedList ( n ) ;
カウト << ' \n リンクされたリストの情報: \n ' ;
画面 ( ) ;
カウト << ' \n 反転後の連結リスト \n ' ;
逆リンクリスト ( & ノードオブジェクト ) ;
画面 ( ) ;
戻る 0 ;
}
// このメソッドはリンクされたリストを作成します
空所 createLinkedList ( 整数 n ) {
構造体 ノード * フロントノード、 * 一時ノード ;
整数 値、私 ;
ノードオブジェクト = ( 構造体 ノード * ) malloc ( のサイズ ( 構造体 ノード ) ) ;
もしも ( ノードオブジェクト == ヌル )
カウト << 「メモリを割り当てるのに十分ではありません」 ;
そうしないと {
カウト << 'ノード 1 の情報を入力してください (数字のみ):' ;
食べる >> 価値 ;
ノードオブジェクト - > 価値 = 価値 ;
ノードオブジェクト - > nextNodePtr = ヌル ;
一時ノード = ノードオブジェクト ;
為に ( 私 = 2 ; 私 <= n ; 私 ++ ) {
フロントノード = ( 構造体 ノード * ) malloc ( のサイズ ( 構造体 ノード ) ) ;
// リンクされたリストにノードがない場合
もしも ( フロントノード == ヌル ) {
カウト << 「メモリを割り当てられません」 ;
壊す ;
}
そうしないと {
カウト << 'ノードの情報を入力してください' << 私 << ':' ;
食べる >> 価値 ;
フロントノード - > 価値 = 価値 ;
フロントノード - > nextNodePtr = ヌル ;
一時ノード - > nextNodePtr = フロントノード ;
一時ノード = 一時ノード - > nextNodePtr ;
}
}
}
}
空所 逆リンクリスト ( ノード ** ノードオブジェクト ) {
構造体 ノード * 一時ノード = ヌル ;
構造体 ノード * 前のノード = ヌル ;
構造体 ノード * 現在のノード = ( * ノードオブジェクト ) ;
その間 ( 現在のノード ! = ヌル ) {
一時ノード = 現在のノード - > nextNodePtr ;
現在のノード - > nextNodePtr = 前のノード ;
前のノード = 現在のノード ;
現在のノード = 一時ノード ;
}
( * ノードオブジェクト ) = 前のノード ;
}
空所 画面 ( ) {
構造体 ノード * 一時ノード ;
もしも ( ノードオブジェクト == ヌル ) {
カウト << 「リンクリストが空です」 ;
}
そうしないと {
一時ノード = ノードオブジェクト ;
その間 ( 一時ノード ! = ヌル )
{
カウト << 一時ノード - > 価値 << ' \t ' ;
一時ノード = 一時ノード - > nextNodePtr ;
}
}
カウト << エンドル ;
}
出力
作成するノードの数 =>: 6ノード 1 の情報を入力してください (数字のみ): 101
ノード 2 の情報を入力してください: 95
ノード 3 の情報を入力してください: 61
ノード 4: 19 の情報を入力してください
ノード 5: 12 の情報を入力してください
ノード 6: 11 の情報を入力してください
リンクされたリストの情報:
101 95 61 19 12 11
反転後の連結リスト
11 12 19 61 95 101
結論
この LinuxHint の記事では、C++ でリンクされたリストを逆にする方法を確認しました。連結リストを逆にする方法は他にもいくつかありますが、これは連結リストを逆にする非常に一般的な方法です。問題をどのように解決したいかを決めるのはあなた次第ですが、一般に、逆リンク リスト関数はポインター スワップを伴う単純なループにする必要があります。