Pythonで連結リストをk個ずつのグループに分けて反転させる方法

片方向連結リストと整数 k が与えられたとき、リストを先頭から k 個ずつの連続するグループに分割し、それぞれのグループ内でノードの並びを反転させる問題を考えます。

たとえば、入力が List = [1,2,3,4,5,6,7,8,9,10]、k = 3 の場合、出力は [3, 2, 1, 6, 5, 4, 9, 8, 7, 10] となります。3個ごとに区切られた各グループが逆順になっており、余った要素（この例では最後の 10）は元の順序のまま保持される点に注目してください。

アルゴリズムの流れ

この問題を解くには、次の手順に従います。

• 値 0 を持つダミーノード tmp を作成し、tmp の次に元の先頭ノードを接続します。
• prev := null、curr := null として初期化します。
• lp（前グループの末尾）、lc（現在グループの先頭）を設定します。
• カウンタ cnt := k とします。
• curr が null でない限り、以下を繰り返します。
  • prev を null にリセットします。
  • cnt > 0 かつ curr が null でない限り、以下を繰り返します。
    • following := curr の次のノード
    • curr のポインタを prev に向けます（リンクの反転）
    • prev := curr、curr := following と更新
    • cnt を 1 減らします。
  • 前グループの末尾 lp の次を prev（反転後のグループの新しい先頭）につなぎ、lc の次を curr につなぎます。
  • lp := lc、lc := curr と更新します。
  • cnt を k に戻します。
• 最後に tmp の次のノード（新しい先頭）を返します。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

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, k):
        tmp = ListNode(0)
        tmp.next = node
        prev, curr = None, node
        lp, lc = tmp, curr
        cnt = k
        while curr:
            prev = None
            while cnt > 0 and curr:
                following = curr.next
                curr.next = prev
                prev, curr = curr, following
                cnt -= 1
            lp.next, lc.next = prev, curr
            lp, lc = lc, curr
            cnt = k
        return tmp.next

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

入力

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

出力

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

この手法では、ダミーノードを使うことで先頭グループの扱いを統一でき、各グループ内でポインタを順次付け替えることで O(n) の時間計算量で反転を実現できます。追加のデータ構造が必要ないため、空間計算量も O(1) に抑えられるのが大きな利点です。