C++ में दो नंबर जोड़ें II

मान लीजिए कि हमारे पास दो गैर-रिक्त लिंक्ड सूचियां हैं जो दो गैर-ऋणात्मक पूर्णांकों का प्रतिनिधित्व करती हैं। यहां सबसे महत्वपूर्ण अंक पहले आता है और उनके प्रत्येक नोड में एक अंक होता है। हमें दो नंबरों को एड करना है और इसे एक लिंक्ड लिस्ट के रूप में वापस करना है। इसलिए यदि सूचियाँ [7, 2, 4, 3] + [5, 6, 4] हैं, तो परिणाम [7, 8, 0, 7]

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

• डमी नामक नोड बनाएं, और मान 0 स्टोर करें, स्टैक s1 और s2 बनाएं।

• s1 को l1 के नोड्स से भरें और s2 को s2 के नोड्स से भरें।

• योग :=0

• जबकि s1 खाली नहीं है या s2 खाली नहीं है

  • यदि s1 खाली है, तो योग :=योग + s1 का शीर्ष मान, स्टैक s1 से हटाएं

  • यदि s2 खाली है, तो योग :=योग + s2 का शीर्ष मान, स्टैक s2 से हटाएं

  • डमी का मूल्य:=योग मॉड 10

  • नया नोड :=योग/10 के साथ एक नया नोड बनाएं

  • नए नोड के आगे :=डमी

  • डमी :=नया नोड

  • योग :=योग / 10

• यदि डमी मान 0 है, तो डमी के आगे वापस आएं, अन्यथा डमी।

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