Thêm hai số II trong C ++

Giả sử chúng ta có hai danh sách liên kết không rỗng đại diện cho hai số nguyên không âm. Ở đây chữ số quan trọng nhất đứng trước và mỗi nút của chúng chứa một chữ số duy nhất. Chúng tôi phải adf hai số và trả về nó dưới dạng một danh sách được liên kết. Vì vậy, nếu danh sách là [7, 2, 4, 3] + [5, 6, 4], thì kết quả sẽ là [7, 8, 0, 7]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một nút có tên là dummy và lưu trữ giá trị 0, tạo các ngăn xếp s1 và s2.

• điền s1 bởi các nút của l1 và điền s2 bởi các nút của s2.

• tổng:=0

• trong khi s1 không trống hoặc s2 không trống

  • nếu s1 trống, thì sum:=sum + giá trị hàng đầu của s1, xóa khỏi ngăn xếp s1

  • nếu s2 trống, thì sum:=sum + giá trị hàng đầu của s2, xóa khỏi ngăn xếp s2

  • giá trị của dummy:=sum mod 10

  • nút mới:=tạo một nút mới với giá trị sum / 10

  • tiếp theo của nút mới:=dummy

  • dummy:=nút mới

  • sum:=sum / 10

• nếu giá trị giả là 0, thì trả về giá trị tiếp theo của giá trị giả, nếu không thì trả về giá trị giả.

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[7,2,4,3]
[5,6,4]

Đầu ra

[7, 8, 0, 7, ]