मान लीजिए हमारे पास एक सिंगली लिंक्ड लिस्ट और एक मान x है; हमें एक जोड़ी ढूंढनी है जिसका योग x के समान हो। हमें यह ध्यान रखना होगा कि हम किसी अतिरिक्त स्थान का उपयोग नहीं कर सकते और अपेक्षित समय जटिलता O(n) होगी।
तो, यदि इनपुट 4→7→8→9→10→11→12, x = 19 जैसा है, तो आउटपुट [(7, 12), (8, 11), (9, 10)] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक फ़ंक्शन convert_to_xor() परिभाषित करें, यह start लेगा,
prev := NULL
जब तक start NULL नहीं है, करें -
next_list_node := start का next
start का next := next_list_node और prev के पते का XOR
prev := start
start := next_list_node
मुख्य विधि से, निम्नलिखित करें -
first := start
next_list_node := NULL, prev := NULL, second := start
जब तक second का next prev के बराबर नहीं है, करें -
temp := second
second := (second के next, prev) के पते का XOR
prev := temp
next_list_node := NULL
prev := NULL
flag := false
जब तक (first NULL के बराबर नहीं है और second NULL के बराबर नहीं है और first second के बराबर नहीं है और first next_list_node के बराबर नहीं है), करें -
यदि first का डेटा + second का डेटा x के समान है, तो -
जोड़ी first का डेटा, second का डेटा प्रदर्शित करें
flag := true
temp := first
first := (first के next, prev) के पते का XOR
prev := temp
temp := second
second := (second के next, next_list_node) के पते का XOR
next_list_node := temp
अन्यथा
यदि first का डेटा + second का डेटा < x, तो
temp := first
first := (first के next, prev) के पते का XOR
prev := temp
अन्यथा
temp := second
second := (second के next, next_list_node) के पते का XOR
next_list_node := temp
यदि flag 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 << "कोई जोड़ी नहीं मिली" << 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)
