用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中删除
虚拟值：=summod10
新节点：=用值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, ]