Pythonで連結リストの先頭N個の要素だけを反転するプログラム

連結リスト（リンクリスト）の中から、指定した範囲の要素だけを反転したい場面はよくあります。本記事では、reverse_list というメソッドを定義し、リストを走査しながら先頭のN個の要素のみを逆順に並べ替える方法を解説します。

それでは、実際のコード例を見ていきましょう。

サンプルコード

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

class LinkedList_structure:
    def __init__(self):
        self.head = None
        self.last_node = None

    def add_vals(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next

    def print_it(self):
        curr = self.head
        while curr:
            print(curr.data)
            curr = curr.next

def reverse_list(my_list, n):
    if n == 0:
        return
    before_val = None
    curr = my_list.head
    if curr is None:
        return
    after_val = curr.next
    for i in range(n):
        curr.next = before_val
        before_val = curr
        curr = after_val
        if after_val is None:
            break
        after_val = after_val.next
    my_list.head.next = curr
    my_list.head = before_val

my_instance = LinkedList_structure()
my_list = input('Enter the elements of the linked list... ').split()
for elem in my_list:
    my_instance.add_vals(int(elem))
n = int(input('Enter the number of elements you wish to reverse in the list... '))

reverse_list(my_instance, n)

print('The new list is : ')
my_instance.print_it()

実行結果

Enter the elements of the linked list... 45 67 89 12 345
Enter the number of elements you wish to reverse in the list... 3
The new list is :
89
67
45
12
345

コードの解説

• Nodeクラスの作成： まず、連結リストの各ノードを表す Node クラスを作成します。各ノードはデータ（data）と次のノードへの参照（next）を持ちます。

• LinkedList_structureクラスの作成： 次に、必要な属性を持つ LinkedList_structure クラスを定義します。

• 初期化処理： __init__ メソッドにより、リストの先頭要素である head を None として初期化します。あわせて末尾ノード last_node も管理することで、要素の追加を効率化しています。

• add_valsメソッド： リストの末尾に新しい値を追加するためのメソッドです。リストが空の場合は新規ノードを head に設定し、そうでなければ末尾ノードの next に接続します。

• print_itメソッド： 連結リストの全要素を順番にコンソールへ表示するためのメソッドです。

• reverse_listメソッド： 本記事の核心となる部分です。3つのポインタ（before_val、curr、after_val）を使いながらリストを走査し、先頭からN個分のノードの向きを一つずつ付け替えていくことで、部分反転を実現します。Nが0の場合やリストが空の場合は何もせずに終了する安全策も組み込まれています。

• インスタンスの生成と入力： LinkedList_structure のインスタンスを作成し、ユーザーから入力された値を順に連結リストへ追加します。

• 反転数の指定： 反転したい要素の個数Nをユーザーから受け取ります。

• 実行と結果表示： reverse_list メソッドを呼び出して反転処理を行い、その結果をコンソールに出力します。

この例では、「45 67 89 12 345」という5つの要素を持つ連結リストに対して、先頭3つの要素を反転するよう指定しています。その結果、「89 67 45 12 345」というリストが出力され、先頭部分だけが正しく逆順になっていることが確認できます。