Pythonで連結リストを昇順にソートするプログラムの書き方

問題の概要

連結リスト（リンクリスト）が与えられたとき、そのリストを昇順に並べ替えることを考えます。

例えば、入力が [5, 8, 4, 1, 5, 6, 3] の場合、出力は [1, 3, 4, 5, 5, 6, 8] となります。

解決のアプローチ

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

1. 新しい空のリスト values を用意します。
2. head に先頭ノードへの参照を保存しておきます。
3. node が null でない間、次の処理を繰り返します。
   • node の値を values の末尾に追加します。
   • node を次のノードに進めます。
4. values を昇順にソートします。
5. values の要素から両端キュー（collections.deque）を作成します。
6. node を先頭ノード head に戻します。
7. node が null でない間、次の処理を繰り返します。
   • キューの左端から要素を取り出して削除し、その値を node の値として設定します。
   • node を次のノードに進めます。
8. head を返します。

このアプローチのポイントは、ノード同士のリンク構造を一切変更せず、各ノードが保持している「値」だけを入れ替えている点です。ポインタのつなぎ替えが必要ないため、実装が非常にシンプルになります。

実装例

より理解を深めるために、以下の実装を見てみましょう。

import collections

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):

        values = []
        head = node
        while node:
            values.append(node.val)
            node = node.next

        values.sort()
        values = collections.deque(values)

        node = head
        while node:
            node.val = values.popleft()
            node = node.next

        return head

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

入力

[5, 8, 4, 1, 5, 6, 3]

出力

[1, 3, 4, 5, 5, 6, 8]

計算量について

このアルゴリズムでは、まず全ノードを一度走査して値を収集し（O(n)）、続いてソートを実行し（O(n log n)）、最後にもう一度ノードを走査して値を書き戻します（O(n)）。したがって、全体の時間計算量は O(n log n)、空間計算量は O(n) となります。

マージソートなどを使ってリンクリストを直接ソートする方法もありますが、本手法はノードの接続関係を壊さずに済むため、コードの可読性と実装の容易さという点で大きなメリットがあります。