这里我们将看到如何将存储在单独链表中的两个数字相加。在链表中，存储了数字的每一位数字。如果数字是 512，那么它将像下面一样存储 -
512 = (5)-->(1)-->(2)-->NULL
登录后复制
我们提供了两个这种类型的列表，我们的任务是将它们相加并在计算总和后得到结果。这里我们使用C++ STL链表。让我们看看算法来下注更好的想法。
算法
addListNumbers(l1, l2)
Begin
Adjust the l1 and l2 lengths by adding leading 0s with the smaller one
carry := 0
res := an empty list
for each node n from l1, scan from last to first, do
item := (l1.item + l2.item + carry) mod 10
insert item at the beginning of res
carry := (l1.item + l2.item + carry) / 10
done
if carry is not 0, then
add carry at the beginning of res
end if
return res
End
登录后复制
示例
#include
#include
using namespace std;
list addListNumbers(list l1, list l2){
//add leading 0s to the shortest number to make them equal length
if(l1.size() > l2.size()){
for(int i = l2.size(); i != l1.size(); i++){
l2.push_front(0);
}
}else if(l1.size() < l2.size()){
for(int i = l1.size(); i != l2.size(); i++){
l1.push_front(0);
}
}
list::reverse_iterator it1 = l1.rbegin();
list::reverse_iterator it2 = l2.rbegin();
list result;
int carry = 0;
while(it1 != l1.rend()){
result.push_front((*it1 + *it2 + carry) % 10);
carry = (*it1 + *it2 + carry) / 10;
it1++; it2++;
}
if(carry != 0){
result.push_front(carry);
}
return result;
}
list numToList(int n){
list numList;
while(n != 0){
numList.push_front(n % 10);
n /= 10;
}
return numList;
}
void displayListNum(list numList){
for(list::iterator it = numList.begin(); it != numList.end();
it++){
cout
