数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++实现两数相加 II
假设我们有两个非空的链表，分别表示两个非负整数。这里最高位数字排在最前，每个节点包含单个数字。我们需要将这两个数字相加，并将其结果作为链表返回。例如，如果链表是 [7, 2, 4, 3] + [5, 6, 4]，则结果将是 [7, 8, 0, 7]
为了解决这个问题，我们将遵循以下步骤：
创建一个名为 dummy 的节点，并将其值存储为 0，创建堆栈 s1 和 s2。
用 l1 的节点填充 s1，用 l2 的节点填充 s2。
sum := 0
当 s1 不为空或 s2 不为空时
如果 s1 为空，则 sum := sum + s1 的顶部值，从堆栈 s1 中删除。
如果 s2 为空，则 sum := sum + s2 的顶部值，从堆栈 s2 中删除。
dummy 的值 := sum mod 10
新节点 := 创建一个值为 sum/10 的新节点
新节点的 next := dummy
dummy := 新节点
sum := sum / 10
如果 dummy 的值为 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, ]
更新于：2020年5月2日
291 次浏览
广告