C++で補助領域なしにソート済み単方向リンクリストから指定した合計になるペアを検索する方法

問題の概要

ソート済みの単方向リンクリストと値 x が与えられたとします。このとき、ノードのデータの合計が x と等しくなるペアをすべて見つける必要があります。ただし、追加の補助領域（余分なメモリ）を使用することはできず、期待される時間計算量は O(n) です。

例として、入力が 4→7→8→9→10→11→12 で、x = 19 の場合、出力は (7, 12)、(8, 11)、(9, 10) となります。

解決のアプローチ：XORリンクリストの活用

配列であれば「両端から中央へ向かう2ポインタ法」で簡単に解けますが、単方向リンクリストは逆方向へ移動できません。そこで、各ノードの next ポインタに「前のノードと次のノードのアドレスのXOR値」を格納する XORリンクリスト に変換します。これにより、補助メモリをほとんど使わずに双方向の走査が可能になり、O(n) 時間で問題を解決できます。

アルゴリズムの手順

ステップ1：convert_to_xor() 関数 — リストをXORリンクリストへ変換します。

• prev を NULL で初期化します。
• start が NULL でない間、以下を繰り返します。
  • next_list_node := start の次のノード
  • start の next := next_list_node のアドレス XOR prev のアドレス
  • prev := start
  • start := next_list_node

ステップ2：メイン処理

• first := start（先頭から順方向へ走査するポインタ）
• next_list_node := NULL、prev := NULL、second := start
• second の next が prev と等しくなるまで、second を末尾まで移動します。
  • temp := second
  • second := (second の next) XOR prev
  • prev := temp
• next_list_node := NULL、prev := NULL、flag := false と初期化します。
• first が NULL でなく、second が NULL でなく、first ≠ second かつ first ≠ next_list_node である間、以下を繰り返します。
  • first のデータ + second のデータ == x の場合：
    • ペア (first のデータ, second のデータ) を表示し、flag := true とします。
    • first を順方向へ、second を逆方向へそれぞれ1つ進めます。
  • それ以外の場合：
    • 合計が x より小さければ、first を順方向へ進めます。
    • 合計が x より大きければ、second を逆方向へ進めます。
• flag が false のままの場合、「ペアが見つかりません」と表示します。

C++での実装例

以下の実装を見ると、理解が深まります。

#include<bits/stdc++.h>
using namespace std;
class ListNode {
public:
    int data;
    ListNode *next;
    ListNode(int data) {
        this->data = data;
        next = NULL;
    }
};
ListNode *make_list(vector<int> v) {
    ListNode *start = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode *ptr = start;
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return start;
}
ListNode* XOR (ListNode *a, ListNode *b) {
    return (ListNode*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}
void convert_to_xor(ListNode *start) {
    ListNode *next_list_node;
    ListNode *prev = NULL;
    while (start != NULL) {
        next_list_node = start->next;
        start->next = XOR(next_list_node, prev);
        prev = start;
        start = next_list_node;
    }
}
void get_pared_sum(ListNode *start, int x) {
    ListNode *first = start;
    ListNode *next_list_node = NULL, *prev = NULL;
    ListNode *second = start;
    while (second->next != prev) {
        ListNode *temp = second;
        second = XOR(second->next, prev);
        prev = temp;
    }
    next_list_node = NULL;
    prev = NULL;
    bool flag = false;
    while (first != NULL && second != NULL && first != second && first != next_list_node) {
        if ((first->data + second->data)==x) {
            cout << "(" << first->data << ","<< second->data << ")" << endl;
            flag = true;
            ListNode *temp = first;
            first = XOR(first->next,prev);
            prev = temp;
            temp = second;
            second = XOR(second->next, next_list_node);
            next_list_node = temp;
        }
        else{
            if ((first->data + second->data) < x) {
                ListNode *temp = first;
                first = XOR(first->next,prev);
                prev = temp;
            }
            else{
                ListNode *temp = second;
                second = XOR(second->next, next_list_node);
                next_list_node = temp;
            }
        }
    }
    if (flag == false)
        cout << "No pair found" << endl;
}
int main() {
    vector<int> v = {4,7,8,9,10,11,12};
    ListNode* start = make_list(v);
    int x = 19;
    convert_to_xor(start);
    get_pared_sum(start,x);
}

入力

{4,7,8,9,10,11,12}

出力

(7,12)
(8,11)
(9,10)

計算量のまとめ

時間計算量は、リストの変換に O(n)、ペアの探索にも O(n) かかるため、全体で O(n) となります。空間計算量については、XORリンクリストが既存の next ポインタを再利用するため、補助領域は O(1) で済みます。この手法を活用すれば、単方向リンクリストでも追加メモリなしに効率的な双方向探索が実現できます。