เพิ่มสองตัวเลข II ใน C ++

สมมติว่าเรามีรายการที่เชื่อมโยงที่ไม่ว่างเปล่าสองรายการซึ่งแสดงถึงจำนวนเต็มที่ไม่ติดลบสองจำนวน ในที่นี้ หลักที่สำคัญที่สุดมาก่อน และแต่ละโหนดมีตัวเลขหลักเดียว เราต้องบวกตัวเลขทั้งสองแล้วส่งคืนเป็นรายการที่เชื่อมโยง ดังนั้นหากรายการคือ [7, 2, 4, 3] + [5, 6, 4] ผลลัพธ์จะเป็น [7, 8, 0, 7]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างโหนดที่เรียกว่า dummy และเก็บค่า 0 สร้าง stacks s1 และ s2

• เติม s1 ด้วยโหนดของ l1 และเติม s2 ด้วยโหนดของ s2

• ผลรวม :=0

• ในขณะที่ s1 ไม่ว่างหรือ s2 ไม่ว่างเปล่า

  • ถ้า s1 ว่างเปล่า sum :=sum + ค่าสูงสุดของ s1 ให้ลบออกจาก stack s1

  • ถ้า s2 ว่างเปล่า sum :=sum + ค่าสูงสุดของ s2 ให้ลบออกจาก stack s2

  • ค่าของหุ่น :=sum mod 10

  • โหนดใหม่ :=สร้างโหนดใหม่ด้วยค่า sum/10

  • ถัดไปของโหนดใหม่ :=ดัมมี่

  • dummy :=โหนดใหม่

  • ผลรวม :=ผลรวม / 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, ]