Pythonで連結リストの隣接ノード間の絶対差が1かどうかを判定する方法

整数値を格納したノードからなる単方向連結リストが与えられたとき、隣り合うノード同士の値の絶対差がすべて「1」になっているかどうかを判定する問題を考えてみましょう。

たとえば、入力が 5 → 6 → 7 → 8 → 7 → 6 → 5 → 4 のような連結リストだった場合、どの隣接ノード間でも差が1なので、出力は True になります。

解法のアプローチ

この問題は、リストを先頭から順に走査しながら、隣接する2つのノードの値を比較していくことで解決できます。手順は以下の通りです。

• 一時変数 temp に先頭ノード（start_node）を代入する
• temp が null でない限り、以下を繰り返す
  • temp.link が null（最後のノード）なら、ループを抜ける
  • |temp の値 − temp.link の値| が 1 でなければ、False を返す
  • temp を次のノードに進める
• 最後まで条件を満たしていれば、True を返す

このアルゴリズムの計算量は O(n)、必要な追加メモリは O(1) であり、リストの長さに対して線形時間で効率的に動作します。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class link_node:
    def __init__(self, value):
        self.value = value
        self.link = None

def make_list(elements):
    head = link_node(elements[0])
    ptr = head
    for element in elements[1:]:
        ptr.link = link_node(element)
        ptr = ptr.link
    return head

def solve(start_node):
    temp = start_node
    while temp:
        # 最後のノードに到達したら終了
        if temp.link is None:
            break
        # 隣接ノードの絶対差が1でなければ False
        if abs(temp.value - temp.link.value) != 1:
            return False
        temp = temp.link
    return True

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

コードのポイント

• link_node クラスは、値（value）と次ノードへの参照（link）を持つシンプルなノード定義です。
• make_list 関数は、要素のリストを受け取って連結リストを構築します。末尾への追加を O(1) で行うため、ポインタ ptr を使い回しています。
• solve 関数が本体の判定処理です。abs() を使って絶対差を計算し、1以外なら即座に False を返します。

実行結果

入力

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

出力

True

このように、リスト内のすべての隣接ノードの絶対差が1であるため、True が出力されます。もし途中で差が1以外になるノードが存在すれば（例： [1, 2, 5] のような場合）、その時点で False が返されます。