C++で双方向連結リストから指定した合計値となるペアを検索する方法

この問題では、双方向連結リスト（doubly linked list）とある値 sum が与えられます。求められているのは、連結リスト内からデータの合計が sum と一致するペアをすべて見つけ出すことです。

具体例で問題を確認してみましょう。

入力

head − 2 <-> 5 <-> 6 <-> 9 <-> 12
x = 11

出力

(2, 9), (5, 6)

解説

ペア (2, 9) の合計値は 11
ペア (5, 6) の合計値は 11

解法アプローチ 1：ネストしたループによる全探索

最もシンプルな解法は、連結リスト全体を走査し、要素を1つずつ取り出しながら、残りのリスト内に合計が sum となる要素が存在するかを探す方法です。これはネストしたループ（二重ループ）を使うことで実現できます。

実装コード

#include<iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
   struct Node *first = head;
   int pairCount = 0;
   while (first != NULL) {
      struct Node *second = first -> next;
      while(second != NULL){
         if ((first->data + second->data) == sum) {
            pairCount++;
            cout<<"("<<first->data<<", "
            <<second->data<<")\n";
         }
         second = second -> next;
      }
      first = first -> next;
   }
   if (!pairCount)
      cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
   struct Node *temp = new Node;
   temp->data = data;
   temp->next = temp->prev = NULL;
   if (!(*head))
      (*head) = temp;
   else{
      temp->next = *head;
      (*head)->prev = temp;
      (*head) = temp;
   }
}
int main() {
   struct Node *head = NULL;
   insert(&head, 12);
   insert(&head, 9);
   insert(&head, 6);
   insert(&head, 5);
   insert(&head, 2);
   int sum = 11;
   cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
   findSumPairs(head, sum);
   return 0;
}

出力

Pair in the linked list with sum = 11 :
(2, 9)
(5, 6)

この方法は理解しやすい反面、時間計算量が O(n²) となるため、リストが長くなると処理に時間がかかるという欠点があります。

解法アプローチ 2：双ポインタ法（ソート済みリスト向けの効率的な解法）

より効率的なアプローチとして、連結リストがソート済みであることを利用した双ポインタ法があります。この方法では、2つのポインタを使用します。

• start：最初は連結リストの先頭（head）を指す
• end：最初は連結リストの末尾のノードを指す

次に、両ポインタが指す値の合計 sumVal を計算し、指定された sum と比較します。

sumVal > sum の場合：end ポインタを左（前）へ移動
sumVal < sum の場合：start ポインタを右（次）へ移動
sumVal == sum の場合：両方の値を出力し、start ポインタを右へ移動

2つのポインタが交差した時点でループを抜けます。また、見つかったペアの数をカウントしておき、0 であれば「No Such Pairs found !（該当するペアは見つかりませんでした）」と出力します。

この双ポインタ法の時間計算量は O(n) であり、ネストしたループを使う方法よりも大幅に効率的です。

実装コード

#include<iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
   struct Node *start = head;
   struct Node *end = head;
   while (end->next != NULL)
      end = end->next;
   int pairCount = 0;
   while (start != NULL && end != NULL && start != end &&
   end->next != start) {
      if ((start->data + end->data) == sum) {
         pairCount++;
         cout<<"("<<start->data<<", "<<end->data<<")\n";
         start = start->next;
         end = end->prev;
      }
      else if ((start->data + end->data) < sum)
         start = start->next;
      else
         end = end->prev;
   }
   if (!pairCount)
      cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
   struct Node *temp = new Node;
   temp->data = data;
   temp->next = temp->prev = NULL;
   if (!(*head))
      (*head) = temp;
   else{
      temp->next = *head;
      (*head)->prev = temp;
      (*head) = temp;
   }
}
int main() {
   struct Node *head = NULL;
   insert(&head, 12);
   insert(&head, 9);
   insert(&head, 6);
   insert(&head, 5);
   insert(&head, 2);
   int sum = 11;
   cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
   findSumPairs(head, sum);
   return 0;
}

出力

Pair in the linked list with sum = 11 :
(2, 9)
(5, 6)

まとめ

双方向連結リストから指定した合計値となるペアを検索する方法として、計算量 O(n²) のネストループによる全探索と、ソート済みリストに対して適用できる計算量 O(n) の双ポインタ法の2つを紹介しました。双方向連結リストは prev ポインタを持つため、end ポインタを後ろから前に移動できる点が双ポインタ法を適用できる大きな利点です。データ量が多い場合は、双ポインタ法の採用を検討することをおすすめします。