Pythonで連結リストの長さが偶数か奇数かを判定する方法

連結リスト（リンクリスト）が与えられたとき、その長さが偶数か奇数かを判定する方法を解説します。

例えば、head = [5,8,7,4,3,6,4,5,8] のような入力が与えられた場合、ノード数は9個なので、出力は「Odd（奇数）」となります。

アルゴリズムの考え方

この問題は、ポインタを2つずつ進めるテクニックを使うことで、リスト全体を明示的にカウントすることなく効率的に解けます。手順は以下の通りです。

• head が null ではなく、head の次のノードも null でない間、以下を繰り返します。
  • head を「次の次」のノード（2つ先）へ進める
• ループ終了後、head が null になっていれば「Even（偶数）」を返す
• それ以外の場合は「Odd（奇数）」を返す

この方法のポイントは、1回の走査で2ノードずつ進めることにあります。ノード数が偶数の場合、最終的に head はちょうど null に到達し、奇数の場合は最後のノードで止まります。この性質を利用することで、計算量 O(n)・追加メモリ O(1) という非常に効率的な判定が可能になります。

実装コード

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(head):
    while head != None and head.next != None:
        head = head.next.next

    if head == None:
        return "Even"
    return "Odd"

head = make_list([5,8,7,4,3,6,4,5,8])
print(solve(head))

入力

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

出力

Odd