मान लीजिए हमारे पास दो गैर-खाली लिंक्ड सूचियाँ हैं जो दो गैर-ऋणात्मक पूर्णांकों का प्रतिनिधित्व करती हैं। यहां सबसे महत्वपूर्ण अंक पहले आता है और उनके प्रत्येक नोड में एक अंक होता है। हमें दोनों संख्याओं को जोड़ना है और इसे एक लिंक्ड सूची के रूप में लौटाना है।
उदाहरण के लिए, यदि सूचियाँ [7, 2, 4, 3] + [5, 6, 4] हैं, तो परिणाम [7, 8, 0, 7] होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
dummyनामक एक नोड बनाएं, और मान 0 संग्रहीत करें, स्टैकs1औरs2बनाएं।s1कोl1के नोड्स से भरें औरs2कोs2के नोड्स से भरें।sum := 0- जब तक
s1खाली नहीं है याs2खाली नहीं है- यदि
s1खाली है, तोsum := sum + s1 का शीर्ष मान, स्टैकs1से हटाएं - यदि
s2खाली है, तोsum := sum + s2 का शीर्ष मान, स्टैकs2से हटाएं dummy का मान := sum mod 10नया नोड := मान sum/10 के साथ एक नया नोड बनाएंनए नोड का अगला := dummydummy := नया नोडsum := sum / 10
- यदि
- यदि
dummy का मान 0 है, तोdummy का अगलालौटाएं, अन्यथाdummy।
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class ListNode{ public: int val; ListNode *next; ListNode(int data){ val = data; next = NULL; } }; ListNode *make_list(vector<int> v){ ListNode *head = new ListNode(v[0]); for(int i = 1; i<v.size(); i++){ ListNode *ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = new ListNode(v[i]); } return head; } void print_list(ListNode *head){ ListNode *ptr = head; cout << "["; while(ptr){ cout << ptr->val << ", "; ptr = ptr->next; } cout << "]" << endl; } class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummy; dummy = new ListNode(0); stack <ListNode*> s1, s2; while(l1){ s1.push(l1); l1 = l1->next; } while(l2){ s2.push(l2); l2 = l2->next; } int sum = 0; while(!s1.empty() || !s2.empty()){ if(!s1.empty()){ sum += s1.top()->val; s1.pop(); } if(!s2.empty()){ sum += s2.top()->val; s2.pop(); } dummy->val = (sum % 10); ListNode* newNode = new ListNode(sum / 10); newNode->next = dummy; dummy = newNode; sum /= 10; } return dummy->val == 0? dummy->next : dummy; } }; main(){ vector<int> v1 = {7,2,4,3}; ListNode *h1 = make_list(v1); vector<int> v2 = {5,6,4}; ListNode *h2 = make_list(v2); Solution ob; print_list(ob.addTwoNumbers(h1, h2)); }इनपुट
[7,2,4,3] [5,6,4]
आउटपुट
[7, 8, 0, 7, ]