Pythonで連結リストのi番目からj番目までのノードを反転させる方法

問題の概要

連結リストと2つの値 i・j が与えられたとき、i 番目から j 番目までのノードを逆順に並べ替え、更新後のリストを返すことを考えます。

例えば、入力が [1,2,3,4,5,6,7,8,9]、i = 2、j = 6 の場合、出力は次のようになります。

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

アルゴリズムの手順

この問題は、以下の手順で解くことができます。

1. 値が None のダミーノード prev_head を作成し、先頭ノードを指させます。
2. prev を prev_head に、curr を先頭ノードに設定します。
3. i 回だけループし、prev と curr を1つずつ前へ進めます。
4. rev_before に prev を、rev_end に curr を記録します（それぞれ反転区間の直前のノードと反転開始ノードです）。
5. (j − i + 1) 回ループし、各ステップで curr.next を一時変数 tmp に退避させてから curr.next を prev に付け替えることで、ポインタを逆向きにつなぎ替えます。
6. 最後に rev_before.next を prev に、rev_end.next を curr に接続し直します。
7. prev_head.next を返します。

実装例

それでは、実際のコードを見て理解を深めましょう。

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:
    def solve(self, node, i, j):
        prev_head = ListNode(None, node)
        prev, curr = prev_head, node

        for _ in range(i):
            prev, curr = curr, curr.next

        rev_before, rev_end = prev, curr

        for _ in range(j - i + 1):
            tmp = curr.next
            curr.next = prev
            prev, curr = curr, tmp

        rev_before.next, rev_end.next = prev, curr

        return prev_head.next

ob = Solution()
head = make_list([1, 2, 3, 4, 5, 6, 7, 8, 9])
i = 2
j = 6
print_list(ob.solve(head, i, j))

入力

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

出力

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

解説のポイント

この実装では、ダミーノード（prev_head）を導入している点が重要です。これにより、反転開始位置がリストの先頭であっても特別な分岐処理を追加せずに統一的に扱えます。

また、ノードをつなぎ替えるだけで処理が完結するため、新たなリストを作成する必要がなく、時間計算量は O(n)、追加のメモリ消費は O(1) で抑えられる効率的な手法です。