C++-এ সর্টেড সিঙ্গলি লিংকড লিস্টে দেয়া সমের পেয়ার খুঁজে বের করা (এক্সট্রা স্পেস ছাড়া)

একটি সর্টেড সিঙ্গলি লিংকড লিস্ট ও মান x দেওয়া আছে। এক্সট্রা স্পেস ছাড়া (O(1) স্পেস) যেসব পেয়ারের যোগফল x হয় সেগুলো বের করতে হবে। XOR লিংকড লিস্ট টেকনিক ব্যবহার করা হয়।

উদাহরণ

List: 4→7→8→9→10→11→12,  x = 19

আউটপুট: (7,12) (8,11) (9,10)

অ্যালগরিদম

1. সিঙ্গলি লিস্টকে XOR লিংকড লিস্ট-এ কনভার্ট করুন (নেক্সট পয়েন্টারে prev XOR next স্টোর করুন)।
2. দুটি পয়েন্টার first (হেড) ও second (টেইল) নিন।
3. টু-পয়েন্টার টেকনিক লাগিয়ে যোগফল x হলে প্রিন্ট করুন।
4. XOR অপারেশন দিয়ে নেক্সট/প্রিভিয়াস নোডে যান।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

class ListNode {
public:
    int data;
    ListNode* next;
    ListNode(int d) : data(d), next(NULL) {}
};

ListNode* XOR(ListNode* a, ListNode* b) {
    return (ListNode*)((uintptr_t)a ^ (uintptr_t)b);
}

void convertToXOR(ListNode* head) {
    ListNode *next = NULL, *prev = NULL;
    while (head) {
        next = head->next;
        head->next = XOR(next, prev);
        prev = head;
        head = next;
    }
}

void getPairSum(ListNode* head, int x) {
    ListNode *first = head, *second = head;
    ListNode *next = NULL, *prev = NULL;
    while (second->next != prev) {
        ListNode* tmp = second;
        second = XOR(second->next, prev);
        prev = tmp;
    }
    next = NULL; prev = NULL;
    bool found = false;
    while (first && second && first != second && first != next) {
        int sum = first->data + second->data;
        if (sum == x) {
            cout << "(" << first->data << "," << second->data << ")\n";
            found = true;
            ListNode* tmp = first;
            first = XOR(first->next, prev); prev = tmp;
            tmp = second;
            second = XOR(second->next, next); next = tmp;
        } else if (sum < x) {
            ListNode* tmp = first;
            first = XOR(first->next, prev); prev = tmp;
        } else {
            ListNode* tmp = second;
            second = XOR(second->next, next); next = tmp;
        }
    }
    if (!found) cout << "No pair found\n";
}

int main() {
    vector<int> v = {4,7,8,9,10,11,12};
    ListNode* head = new ListNode(v[0]);
    ListNode* cur = head;
    for (int i=1;inext = new ListNode(v[i]); cur = cur->next; }
    convertToXOR(head);
    getPairSum(head, 19);
    return 0;
}

আউটপুট: (7,12) (8,11) (9,10)