सी ++ में अतिरिक्त स्थान के बिना एकल लिंक किए गए क्रमबद्ध में दिए गए योग के लिए जोड़ी खोजें

मान लीजिए कि हमारे पास एक एकल लिंक की गई सूची है और एक मान x है; हमें एक ऐसा जोड़ा खोजना है जिसका योग x के समान हो। हमें यह ध्यान रखना होगा कि हम किसी अतिरिक्त स्थान का उपयोग नहीं कर सकते हैं और अपेक्षित समय जटिलता O(n) होगी।

इसलिए, यदि इनपुट 4→7→8→9→10→11→12, x =19 जैसा है, तो आउटपुट [(7, 12), (8, 11), (9, 10)]<होगा। /पी>

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें Convert_to_xor(), यह प्रारंभ होगा,

• पिछला:=NULL

• जबकि स्टार्ट न्यूल है, करें -

  • next_list_node :=शुरुआत के बाद

  • प्रारंभ के आगे :=next_list_node और पिछला के पते का XOR

  • पिछला:=प्रारंभ

  • प्रारंभ:=next_list_node

• मुख्य विधि से, निम्न कार्य करें -

• पहला :=प्रारंभ

• next_list_node:=NULL, पिछला:=NULL, दूसरा:=प्रारंभ

• जबकि सेकंड का अगला पिछला के बराबर नहीं है, करें -

  • अस्थायी:=सेकंड

  • दूसरा :=के पते का XOR (दूसरे के आगे, पिछला)

  • पिछला:=अस्थायी

• next_list_node:=NULL

• पिछला:=NULL

• झंडा :=झूठा

• जबकि (पहला NULL के बराबर नहीं है और दूसरा NULL के बराबर नहीं है और पहला दूसरे के बराबर नहीं है और पहला next_list_node के बराबर नहीं है), करें -

  • यदि पहले का डेटा + सेकंड का डेटा x के समान है, तो -

    • पहले का युग्म डेटा प्रदर्शित करें, दूसरे का डेटा

    • झंडा :=सच

    • अस्थायी:=पहले

    • पहला :=के पते का XOR (पहले के आगे, पिछला)

    • पिछला:=अस्थायी

    • अस्थायी:=सेकंड

    • दूसरा :=दूसरे के अगले के पते का XOR, next_list_node)

    • next_list_node:=अस्थायी

  • अन्यथा

    • यदि पहले का डेटा + दूसरे का डेटा

      • अस्थायी:=पहले

      • पहला :=के पते का XOR (पहले के आगे, पिछला)

      • पिछला:=अस्थायी

    • अन्यथा

      • अस्थायी:=सेकंड

      • दूसरा :=के पते का XOR (दूसरे के आगे, next_list_node)

      • next_list_node:=अस्थायी

• यदि ध्वज असत्य के समान है, तो -

  • कोई जोड़ी नहीं है

उदाहरण (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)