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

概要

正の相異なる要素で構成されたソート済みの双方向リンクリスト（Doubly Linked List）が与えられたとき、ノード同士の積が指定した値 x と等しくなるペアをすべて見つけるのが本記事の課題です。ポイントは、余分なメモリ領域を使用せずに解くことです。

入力例と出力例

例1

List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9
x = 8

出力：

(1, 8), (2, 4)

例2

List1 = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7
x = 6

出力：

(1, 6), (2, 3)

解法のアプローチ

単純な方法（ナイーブなアプローチ）

最もシンプルな方法は、二重ループでリンクリストを走査し、考えられるすべてのペアを列挙して、積が x に一致するかどうかを確認するものです。この場合の計算量は O(n²) となります（n は双方向リンクリストのノード総数）。ノード数が多い場合は非効率になるため、より良い手法が望まれます。

効率的な解法（ツーポインタ法）

ここでは、計算量 O(n) を実現できる効率的なアルゴリズムを紹介します。手順は以下の通りです。

1. ソート済み双方向リンクリスト内の候補要素を特定するために、2つのポインタ変数を用意します。
2. first1 をリンクリストの先頭（head）で初期化し、second1 を末尾ノード（last_node）で初期化します。
3. リンクリストにはランダムアクセスができないため、second1 を設定するにはリストを一度先頭から走査して末尾ノードを見つける必要があります。
4. 現在の first1 と second1 のデータの積が x より小さい場合は、first1 を前方へ移動します。積が x より大きい場合は、second1 を後方へ移動します。
5. 配列の場合と異なり、ループの終了条件も工夫が必要です。ループは「いずれかのポインタが NULL になったとき」「2つのポインタが交差したとき（second1->next == first1）」「2つのポインタが同一ノードを指したとき（first1 == second1）」のいずれかを満たした時点で終了します。

この手法は、ソート済み配列における「Two Pointer」テクニックを双方向リンクリストに応用したものであり、prev ポインタのおかげで後方への移動も O(1) で行える点が特徴です。

C++による実装例

// C++プログラム：ソート済み双方向リンクリストから
// 指定された積 x となるペアを検索する
#include <bits/stdc++.h>
using namespace std;

// 双方向リンクリストのノード構造体
typedef struct Node1 {
    int data1;
    struct Node1 *next1, *prev1;
} Node1;

// 積が指定値 x と等しくなるペアを検索する関数
void pairProduct(struct Node1* head1, int x1) {
    // 2つのポインタを設定：
    // first1 はDLLの先頭、second1 はDLLの末尾を指す
    struct Node1* first1 = head1;
    struct Node1* second1 = head1;
    while (second1->next1 != NULL)
        second1 = second1->next1;

    // ペアが見つかったかどうかを記録するフラグ
    bool found1 = false;

    // ループ終了条件：いずれかのポインタが NULL になる、
    // 2つのポインタが交差する（second1->next1 == first1）、
    // または同一ノードを指す（first1 == second1）
    while (first1 != NULL && second1 != NULL &&
           first1 != second1 && second1->next1 != first1) {
        // ペアが見つかった場合
        if ((first1->data1 * second1->data1) == x1) {
            found1 = true;
            cout << "(" << first1->data1 << ", "
                 << second1->data1 << ")" << endl;
            // first1 を前方へ移動
            first1 = first1->next1;
            // second1 を後方へ移動
            second1 = second1->prev1;
        } else {
            if ((first1->data1 * second1->data1) < x1)
                first1 = first1->next1;   // 積が小さい → 前進
            else
                second1 = second1->prev1; // 積が大きい → 後退
        }
    }

    // ペアが存在しなかった場合
    if (found1 == false)
        cout << "No pair found";
}

// 双方向リンクリストの先頭に新しいノードを挿入するユーティリティ関数
void insert(struct Node1** head1, int data1) {
    struct Node1* temp1 = new Node1;
    temp1->data1 = data1;
    temp1->next1 = temp1->prev1 = NULL;
    if (!(*head1))
        (*head1) = temp1;
    else {
        temp1->next1 = *head1;
        (*head1)->prev1 = temp1;
        (*head1) = temp1;
    }
}

// ドライバーコード
int main() {
    // 双方向リンクリストを作成
    struct Node1* head1 = NULL;
    insert(&head1, 7);
    insert(&head1, 6);
    insert(&head1, 5);
    insert(&head1, 4);
    insert(&head1, 3);
    insert(&head1, 2);
    insert(&head1, 1);
    int x1 = 6;

    pairProduct(head1, x1);
    return 0;
}

実行結果

(1, 6)
(2, 3)

まとめ

このアルゴリズムでは、各ポインタが最大でもリンクリスト全体を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) となります。ソート済みという前提条件を活かすことで、二重ループによる O(n²) の探索を大幅に高速化できる点が大きな魅力です。双方向リンクリストならではの prev ポインタを活用したテクニックとして、ぜひ覚えておきましょう。