Pythonで片方向連結リストが厳密に昇順かどうかを判定する方法

はじめに

この記事では、Pythonを使って片方向連結リスト（Singly Linked List）の各ノードの値が厳密に昇順（strictly ascending order）に並んでいるかどうかを判定するアルゴリズムを解説します。

「厳密に昇順」とは、隣り合うノードの値が等しくならず、必ず前の値より大きくなっている状態を指します。つまり、a < b < c ... のような並びが必要です。

問題の概要

連結リストの先頭ノード（head）が与えられたとき、すべてのノードの値が厳密な昇順にソートされているかどうかを確認します。

例えば、入力が [2, 61, 105, 157] の場合、各要素は前の要素より大きいため、出力は True になります。一方、途中で同じ値や小さい値が現れた場合は False を返します。

解決アプローチ

この問題は再帰（recursion）を使うことでシンプルに解決できます。手順は以下の通りです。

• 関数 solve() を定義し、引数として先頭ノード head を受け取ります。
• head.next が null（None）の場合、リストの末尾まで到達したことを意味するので True を返します。
• head.val >= head.next.val の場合、昇順が崩れているため False を返します。
• それ以外の場合は、次のノードに対して solve(head.next) を再帰的に呼び出します。

実装例

以下は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

class Solution:
    def solve(self, head):
        if head.next == None:
            return True
        if head.val >= head.next.val:
            return False
        return self.solve(head.next)

ob = Solution()
head = make_list([2,61,105,157])
print(ob.solve(head))

入力

[2,61,105,157]

出力

True

コードの解説

• ListNodeクラス： 連結リストの各ノードを表現します。コンストラクタでデータ（val）と次のノードへの参照（next）を保持します。
• make_list関数： Pythonのリストから連結リストを構築するヘルパー関数です。末尾に新しいノードを追加していきます。
• Solutionクラスのsolveメソッド： 再帰的にノードをたどりながら、現在のノードの値と次のノードの値を比較します。条件を満たさなければ即座に False を返し、最後まで問題なければ True を返します。

計算量について

• 時間計算量： O(n) — リスト内の全ノードを一度ずつ訪問します。
• 空間計算量： O(n) — 再帰呼び出しによりコールスタックを使用します。大きなリストを扱う場合は、whileループによる反復処理に書き換えることでO(1)に抑えられます。

まとめ

連結リストが厳密に昇順になっているかの判定は、再帰または反復処理を使えば簡単に実装できます。隣接するノード同士を比較し、一つでも「以上」の関係が見つかった時点で False を返すのがポイントです。ぜひ自分のコードにも応用してみてください。