Pythonで連結リストが降順にソートされているか判定する方法（反復処理・再帰の両方を解説）

問題の概要

連結リスト（リンクリスト）が与えられたとき、それが降順（非増加順）にソートされているかどうかを判定する2つの関数を定義することを考えます。1つ目の関数は反復処理で動作し、2つ目の関数は再帰呼び出しで動作します。

たとえば、入力が L = [15, 13, 8, 6, 4, 2] の場合、すべての要素が降順に並んでいるため、出力は True となります。

解決のためのアプローチ

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

1. 反復版の関数 solve_iter() を定義します（引数として先頭ノード head を受け取ります）。
   　・head が null（None）の場合は True を返します。
   　・head の次ノードが存在する間、以下を繰り返します。
   　　- current := head とします。
   　　- current の値が current の次ノードの値以下であれば False を返します。
   　　- head := 次ノード として進めます。
   　・ループが完了したら True を返します。
2. 再帰版の関数 solve_rec() を定義します（同様に head を受け取ります）。
   　・head が null、または head の次ノードが null の場合は True を返します（リスト末尾まで確認できたことを意味します）。
   　・「head の値が次ノードの値より大きい」かつ「solve_rec(head の次ノード) が True」のときに True を返し、それ以外は False を返します。

実装例

理解を深めるために、以下の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

def solve_iter(head):
    if head == None:
        return True
    while head.next != None:
        current = head
        if current.val <= current.next.val:
            return False
        head = head.next
    return True

def solve_rec(head):
    if head == None or head.next == None:
        return True
    return head.val > head.next.val and solve_rec(head.next)

L = make_list([15, 13, 8, 6, 4, 2])
print(solve_iter(L))
print(solve_rec(L))

実装のポイント

• 反復版は時間計算量 O(n)、空間計算量 O(1) で効率的に動作します。
• 再帰版のコードは簡潔ですが、リストの長さ分だけコールスタックを消費するため、空間計算量は O(n) になります。長いリストを扱う場合は、Pythonの再帰深度上限（デフォルトで約1000）にも注意が必要です。
• この実装では「現在の値が次の値以下なら未ソート」と判定しているため、隣接する値が等しい場合も False となります。つまり、厳密な降順（各要素が直前の要素より小さい）チェックになっています。

入力

[15, 13, 8, 6, 4, 2]

出力

True
True