Pythonでソート済み双方向連結リストから積が指定値と一致するペアを検索する方法

一意な正の整数で構成されたソート済みの双方向連結リスト（doubly linked list）があるとします。このリストの中から、積が指定された値 x と一致するペアを見つける必要があります。重要なポイントは、余分なメモリ領域を消費せずに解くことです。

例えば、入力が次のような場合を考えてみましょう。

L = 1 ⇔ 2 ⇔ 4 ⇔ 5 ⇔ 6 ⇔ 8 ⇔ 9、x = 8

このとき、出力は (1, 8) と (2, 4) になります。

アルゴリズムの考え方：二ポインタ手法

この問題は、配列の「二ポインタ（two pointer）」テクニックを連結リストに応用することで、O(n) の時間計算量・O(1) の空間計算量で解けます。手順は以下の通りです。

• curr を先頭ノードに、nxt も先頭ノードに設定する。
• nxt.next が None になるまで nxt を末尾まで進める（末尾ノードへのポインタを取得）。
• フラグ found を False で初期化する。
• curr と nxt がどちらも有効で、かつ互いに異なり、nxt.next が curr ではない間、以下を繰り返す。
  • curr.data * nxt.data == x の場合：
    found を True にし、ペア (curr.data, nxt.data) を表示して、curr を次へ、nxt を前へ移動する。
  • 積が x より小さい場合：
    積を大きくするために curr を次のノードへ進める。
  • 積が x より大きい場合：
    積を小さくするために nxt を前のノードへ戻す。
• ループ終了後も found が False の場合は、「Not found（見つかりません）」と表示する。

リストが昇順にソートされているため、「先頭から進むポインタ」と「末尾から戻るポインタ」を使うことで、積の大小関係に応じて効率的に探索範囲を絞り込めるのがこの手法のポイントです。

Pythonでの実装例

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

class ListNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

def insert(head, data):
    node = ListNode(data)
    node.next = node.prev = None
    if head is None:
        head = node
    else:
        node.next = head
        head.prev = node
        head = node
    return head

def get_pair_prod(head, x):
    curr = head
    nxt = head
    # 末尾ノードまで移動
    while nxt.next is not None:
        nxt = nxt.next

    found = False
    while curr is not None and nxt is not None \
            and curr != nxt and nxt.next != curr:
        if curr.data * nxt.data == x:
            found = True
            print("(", curr.data, ",", nxt.data, ")")
            curr = curr.next
            nxt = nxt.prev
        elif curr.data * nxt.data < x:
            curr = curr.next
        else:
            nxt = nxt.prev

    if not found:
        print("Not found")

# リストの構築
head = None
for val in [9, 8, 6, 5, 4, 2, 1]:
    head = insert(head, val)

x = 8
get_pair_prod(head, x)

入力

head = None
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8

出力

( 1 , 8 )
( 2 , 4 )

計算量について

• 時間計算量： O(n)。各ポインタは最大でもリスト全体を一度ずつ走査するためです。
• 空間計算量： O(1)。追加のデータ構造を使用しないため、問題の制約「余分な領域を使わない」を満たしています。

このように、双方向連結リストの prev ポインタを活用すれば、ハッシュセットなどを使わずに、ソート済みリスト上で効率的にペア検索を行うことができます。