Python でリンクリストを逆にする

リンクリストは、要素の一定時間の追加と削除を提供するコンピュータサイエンスの線形データ構造です。ノードで構成されています。

1つのノードには、いくつかのデータと次のノードのアドレスが格納されます。次のノードは、そのデータと次のノードのアドレスを格納します。単一のノードは、それが指しているノードについてのみ知っています。それを指しているノードに関する情報はありません。

この構造により、配列を新しい配列にコピーしたり、配列の要素をシフトして追加と削除の余地を作成したりする必要がある配列とは異なり、新しいノードを追加したり、既存のノードを一定時間で削除したりできます。

配列では、インデックスを使用して一定時間で要素にアクセスできます。ただし、リンクリストの場合、要素にアクセスするのに O(n) の時間がかかります。ここで、n はリンクリストの長さです。

リンクリストは構造（線形）の点で配列に似ているため、リンクリストの並べ替え、フィルタリング、検索などの操作も実行できます。バブルソート、挿入ソート、マージソート、クイックソート、選択ソート、バイナリ検索、リンクリストの線形検索などのソートおよび検索アルゴリズムを使用できます。

この記事では、Python を使用してリンクリストを逆にする方法を説明します。コードスニペットは、リンクリストのブロックを表す Node クラスを考慮していることに注意してください。

Node クラスは次のようになります。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Python でリンクリストを逆にする

Python でリンクリストを逆にするには、次の Python コードを参照してください。

def reverse(head: Node) -> Node:
    previous = None
    current = head
    next = None

    while current is not None:
        next = current.next
        current.next = previous
        previous = current
        current = next

    head = previous
    return head

コードを理解するために、リンクリストの例 1-> 2-> 3-> 4-> 5->なしを考えてみましょう。

最初に、入力リンクリストの先頭である None、および None をそれぞれ指す 3つの変数、previous、current、および next を宣言します。次に、current ノードが None を指しているときに終了する while ループを宣言します。

反復ごとに：

• current ノードの次のノードを next ノードに保存します。
• 現在のノードの次のノードを前のノードに設定します。
• 前のノードを現在のノードにリセットします。
• 現在のノードを次のノードにリセットします。

次の表は、上記の例にアルゴリズムを適用したときに、変数の値、つまり前へ、現在、および次へがどのように変化するかを示しています。

|| previous | current | next |
| ———- | ——— | —— |
| None | 1 | None |
| 1 | 2 | 2 |
| 2 | 3 | 3 |
| 3 | 4 | 4 |
| 4 | 5 | 5 |
| 5 | None | None |

上のテーブルセルには、ノードによって保存されている値が表示されます。