用C ++加上两个数字II

假设我们有两个表示两个非负整数的非空链表。在这里，最高有效位在前，每个节点都包含一个数字。我们必须将两个数字adf并将其作为链表返回。因此，如果列表为[7、2、4、3] + [5、6、4]，则结果将为[7、8、0、7]

为了解决这个问题，我们将遵循以下步骤-

• 创建一个称为虚拟节点，并存储值0，创建堆栈s1和s2。

• 用l1的节点填充s1，用s2的节点填充s2。

• 和：= 0

• s1不为空或s2不为空

• 如果s1为空，则sum：= sum + s1的最大值，从堆栈s1中删除

• 如果s2为空，则sum：= sum + s2的最大值，从堆栈s2中删除

• 虚拟值：= sum mod 10

• 新节点：=用值sum / 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, ]