Pythonで連結リストを逆順に反転するプログラム【再帰を使った実装方法】

はじめに

連結リスト（リンクリスト）が与えられたとき、それを逆順に並べ替えることを考えます。例えば、リストが 2 → 4 → 6 → 8 の場合、反転後の新しいリストは 8 → 6 → 4 → 2 となります。

本記事では、再帰処理を用いてこの問題を解く方法を、アルゴリズムの考え方から実際のコードまで詳しく解説します。

解決のためのアプローチ

この問題は、各ノードの next ポインタの向きを先頭から順番に付け替えていくことで解決できます。具体的には、以下の手順に従います。

• solve(head, back) という手続きを定義し、リストの反転を再帰的に行う
• head が存在しない（空の）場合は、head をそのまま返して終了
• temp := head.next — 次のノードへの参照を一時的に保存する
• head.next := back — 現在のノードの向きを前のノードへと反転させる
• back := head — 反転済み部分の先頭として現在のノードを記録する
• temp が空（末尾に到達した）なら、head を返して終了
• head := temp — 処理対象を次のノードへ進める
• solve(head, back) を再帰的に呼び出す

実装例

それでは、実際のPythonコードを見てみましょう。

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

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def print_list(head):
    ptr = head
    print('[', end="")
    while ptr:
        print(ptr.val, end=", ")
        ptr = ptr.next
    print(']')

class Solution(object):
    def reverseList(self, head):
        return self.solve(head, None)

    def solve(self, head, back):
        if not head:
            return head
        temp = head.next
        head.next = back
        back = head
        if not temp:
            return head
        head = temp
        return self.solve(head, back)

list1 = make_list([5, 8, 9, 6, 4, 7, 8, 1])
ob1 = Solution()
list2 = ob1.reverseList(list1)
print_list(list2)

コードのポイント

• ListNode クラス：値（val）と次ノードへの参照（next）を持つ、連結リストの基本構造です。
• make_list 関数：通常の配列から連結リストを生成するためのヘルパー関数です。
• solve メソッド：引数 head で現在処理中のノード、back で既に反転済みの部分リストの先頭を受け取り、再帰的にポインタの向きを入れ替えていきます。初期呼び出しでは back に None を渡します。

入力

[5,8,9,6,4,7,8,1]

出力

[1, 8, 7, 4, 6, 9, 8, 5]

計算量について

• 時間計算量： O(n) — 各ノードを一度だけ訪問します。
• 空間計算量： O(n) — 再帰呼び出しによるスタック領域が必要になります。

なお、再帰の深さ制限が気になる場合や大規模なデータを扱う場合は、ループを使った反復的な実装（空間計算量 O(1)）も検討するとよいでしょう。

まとめ

連結リストの反転は、ポインタ操作の基礎を学ぶ上で非常に重要なテーマです。再帰を使えば「残りのリストはすでに反転されているものとして扱う」というシンプルな発想でエレガントに実装できます。ぜひ自分でも手を動かして、ノードのつながりがどう変化していくのかを追ってみてください。