দুটি নন-এম্পটি লিংকড লিস্ট দেওয়া আছে যেগুলো দুটি নন-নেগেটিভ পূর্ণসংখ্যা রিপ্রেজেন্ট করে। সবচেয়ে σημαντपूर्ण ডিজিট আগে আসে এবং প্রতিটি নোডে একক ডিজিট থাকে। দুটি সংখ্যা যোগ করে ফলাফল লিংকড লিস্ট আকারে ফেরত দিন। উদাহরণ: [7,2,4,3] + [5,6,4] হলে ফলাফল [7,8,0,7]।
সমাধানের ধাপগুলো:
- একটি ডামি নোড বানান ভ্যালু ০ দিয়ে, দুটি স্ট্যাক
s1, s2। s1-কেl1-এর নোড দিয়ে,s2-কেl2-এর নোড দিয়ে ফিল করুন।sum := 0s1বাs2খালি না হওয়া পর্যন্ত:- যদি
s1খালি না হয়,sum += s1.top()->val, s1.pop() - যদি
s2খালি না হয়,sum += s2.top()->val, s2.pop() dummy->val = sum % 10- নতুন নোড বানান ভ্যালু
sum/10দিয়ে - নতুন নোডের
next := dummy dummy := নতুন নোডsum := sum / 10
- যদি
- যদি
dummy->val == 0,dummy->nextফেরত দিন, অন্যথায়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, ]
