Pythonで連結リストを反転する方法｜再帰を使った実装をわかりやすく解説

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

解き方のアプローチ

この問題は、再帰を使った手順「solve(head, back)」を定義することで解決できます。具体的な流れは以下のとおりです。

• リストの反転を再帰的に行う手順 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):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        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([1, 3, 5, 7])
ob1 = Solution()
list2 = ob1.reverseList(list1)
print_list(list2)

入力

list1 = [1,3,5,7]

出力

[7, 5, 3, 1]

処理のポイント

このアルゴリズムでは、各ノードの next ポインタを前のノードに向けることで、リスト全体の向きを反転させています。back 変数が「これまで処理済みの部分リストの先頭」を保持し、再帰呼び出しがリストの末尾に到達した時点で、最後のノードが新しい先頭となり、完全に反転されたリストが完成します。