C ++で余分なスペースなしで、ソートされた単一リンクで指定された合計のペアを検索します

単一リンクリストと値xがあるとします。合計がxと同じペアを見つける必要があります。余分なスペースを使用することはできず、予想される時間計算量はO（n）になることに注意する必要があります。

したがって、入力が4→7→8→9→10→11→12、x =19の場合、出力は[（7、12）、（8、11）、（9、10）]<になります。 / P>

これを解決するには、次の手順に従います-

• 関数convert_to_xor（）を定義します。これで開始されます

• prev：=NULL

• startがNULLの場合、-

  を実行します。

  • next_list_node：=次の開始

  • next of start：=next_list_nodeおよびprevのアドレスのXOR

  • 前：=開始

  • start：=next_list_node

• メインの方法から、次のようにします-

• 最初：=開始

• next_list_node：=NULL、prev：=NULL、second：=start

• 次の秒は前と等しくありませんが、実行-

  • temp：=秒

  • second：=（next of second、prev）のアドレスのXOR

  • 前：=temp

• next_list_node：=NULL

• prev：=NULL

• フラグ：=false

• （firstがNULLに等しくなく、secondがNULLに等しくなく、firstがsecondに等しくなく、firstがnext_list_nodeに等しくない）、do-

  • 最初のデータ+2番目のデータがxと同じである場合、-

    • 最初のペアデータ、2番目のデータを表示

    • フラグ：=true

    • temp：=first

    • first：=（next of first、prev）のアドレスのXOR

    • 前：=temp

    • temp：=秒

    • second：=next of secondのアドレスのXOR、next_list_node）

    • next_list_node：=temp

  • それ以外の場合

    • 最初のデータ+2番目のデータ

      • temp：=first

      • first：=（next of first、prev）のアドレスのXOR

      • 前：=temp

    • それ以外の場合

      • temp：=秒

      • second：=（next of second、next_list_node）のアドレスのXOR

      • next_list_node：=temp

• フラグが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)