C++ এ অতিরিক্ত স্থান ছাড়াই এককভাবে লিঙ্কযুক্ত সাজানো যোগফলের জন্য জোড়া খুঁজুন

ধরুন আমাদের একটি এককভাবে লিঙ্কযুক্ত তালিকা এবং একটি মান x আছে; আমাদের একটি জোড়া খুঁজে বের করতে হবে যার যোগফল x এর সমান। আমাদের মনে রাখতে হবে যে আমরা কোনো অতিরিক্ত স্থান ব্যবহার করতে পারি না এবং প্রত্যাশিত সময়ের জটিলতা হবে O(n).

সুতরাং, যদি ইনপুট হয় 4→7→8→9→10→11→12, x =19, তাহলে আউটপুট হবে [(7, 12), (8, 11), (9, 10)]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• কনভার্ট_টু_এক্সর() একটি ফাংশন সংজ্ঞায়িত করুন, এটি শুরু করবে,

• পূর্ববর্তী :=NULL

• যখন শুরু NULL হয়, −

  করুন

  • next_list_node :=শুরুর পরের

  • শুরুর পরের :=next_list_node এবং prev

    এর ঠিকানার XOR

  • পূর্ববর্তী :=শুরু

  • শুরু :=next_list_node

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• প্রথম :=শুরু

• next_list_node :=NULL, prev :=NULL, second :=start

• সেকেন্ডের পরেরটি আগেরটির সমান না হলে −

  করুন

  • তাপমাত্রা :=সেকেন্ড

  • দ্বিতীয় :=এর ঠিকানার XOR (সেকেন্ডের পরবর্তী, পূর্ববর্তী)

  • পূর্ববর্তী :=temp

• next_list_node :=NULL

• পূর্ববর্তী :=NULL

• পতাকা :=মিথ্যা

• যখন (প্রথমটি NULL এর সমান নয় এবং দ্বিতীয়টি NULL এর সমান নয় এবং প্রথমটি দ্বিতীয়টির সমান নয় এবং প্রথমটি next_list_node-এর সমান নয়), করুন −

  • যদি প্রথমের ডেটা + সেকেন্ডের ডেটা x এর মতো হয়, তাহলে −

    • ডিসপ্লে পেয়ার ডেটা প্রথম, দ্বিতীয় ডেটা

    • পতাকা :=সত্য

    • temp :=প্রথম

    • first :=এর ঠিকানার XOR (প্রথম, পূর্ববর্তী)

    • পূর্ববর্তী :=temp

    • তাপমাত্রা :=সেকেন্ড

    • দ্বিতীয় :=সেকেন্ডের পরের ঠিকানার XOR, next_list_node)

    • next_list_node :=temp

  • অন্যথায়

    • যদি প্রথমের ডেটা + দ্বিতীয়ের ডেটা

      • temp :=প্রথম

      • first :=এর ঠিকানার XOR (প্রথম, পূর্ববর্তী)

      • পূর্ববর্তী :=temp

    • অন্যথায়

      • তাপমাত্রা :=সেকেন্ড

      • দ্বিতীয় :=এর ঠিকানার XOR (সেকেন্ডের পরের, next_list_node)

      • next_list_node :=temp

• যদি পতাকা মিথ্যা হিসাবে একই হয়, তাহলে -

  • কোন জুড়ি নেই

উদাহরণ (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)