Pythonで連結リスト（リンクリスト）の長さを求める方法

単方向連結リスト（片方向リンクリスト）が与えられたとき、その長さ（ノード数）を求めることを考えます。この連結リストは、next（次のノードへの参照）と val（ノードが保持する値）というフィールドを持っています。

例えば、入力が [2 -> 4 -> 5 -> 7 -> 8 -> 9 -> 3] のような連結リストである場合、ノードは7個あるため、出力は 7 となります。

解決のアプローチ

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

• カウンタ変数 count を 0 で初期化する
• 現在のノードが null（None）でない限り、以下を繰り返す
  • count を 1 増やす
  • 現在のノードを次のノード（node.next）に移動する
• ループ終了後、count を返す

このアルゴリズムの計算量は 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

class Solution:
    def solve(self, node):
        count = 0
        while node:
            count += 1
            node = node.next
        return count

ob = Solution()
head = make_list([2,4,5,7,8,9,3])
print(ob.solve(head))

入力

[2,4,5,7,8,9,3]

出力

7

コードの解説

ListNode クラスは連結リストの各ノードを表し、コンストラクタで値（val）と次ノードへの参照（next）を受け取ります。make_list 関数は Python のリストから連結リストを構築する補助関数です。

核心となるのは Solution クラスの solve メソッドです。先頭ノードから順に next をたどりながらカウントを増やしていき、node が None になった時点でのカウント値、すなわちリスト全体の長さを返します。このように、ポインタを一つずつ進めるシンプルな走査によって、連結リストの長さを効率的に求めることができます。