题目描述：You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.（给你两个链表，表示两个非负整数。数字在链表中按反序存储，例如342在链表中为2->4->3。链表每一个节点包含一个数字（0-9）。计算这两个数字和并以链表形式返回。）
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8 （即：342+465= 807）
分析：由上述描述知，要注意以下几点，
（1）因为存储是反过来的，即数字342存成2->4->3，所以要注意进位是向后的；
（2）边界条件：链表l1或l2为空时，直接返回；
（3）链表l1和l2长度可能不同，因此要注意处理某个链表剩余的高位；
（4）2个数相加，可能会产生最高位的进位，因此要注意在完成以上（1）－（3）的操作后，判断进位是否为0，不为0则需要增加结点存储最高位的进位。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* sum;
sum = new ListNode(l1->val + l2->val);
ListNode* p = sum;
l1 = l1->next;
l2 = l2->next;
while(l1 != NULL || l2 != NULL || p->val > 9)
{
p->next = new ListNode(p->val / 10);
p->val %= 10;//判断是否产生进位
p = p->next;
//处理l1或l2可能的剩余高位
if(l1)
{
p->val += l1->val;
l1 = l1->next;
}
if(l2)
{
p->val += l2->val;
l2 = l2->next;
}
}
return sum;
}
};
其他解法：
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
int tmp=0;
ListNode rs(0), *r=&rs, *p=l1, *q=l2;
while(p!=NULL||q!=NULL||tmp){
tmp=tmp+(p==NULL?0:p->val)+(q==NULL?0:q->val);
r->next=new ListNode(tmp%10);
r=r->next;
p=(p==NULL?p:p->next);
q=(q==NULL?q:q->next);
tmp=tmp/10;
}
return rs.next;
}
};
Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
class Solution {
public:
string addBinary(string a, string b) {
string res;
int i = a.size(), j = b.size(), cur = 0;
while(i || j || cur) {
cur += (i ? a[(i--)-1] -'0' : 0) + (j ? b[(j--)-1] -'0' : 0);
res = char(cur%2 + '0') + res;
cur /= 2;
}
return res;
}
};
注：字符在计算机里是用数字表示的，即ascill 码。如：a[1]是'1' ，字符'1'的ascii码是49，而字符'0'的ascii码是48 ，这样a[1]-'0'就是49-48 求得的就是数字1，这样就把a[1]里边存的数字字符转换成了整形数值。
或：（和上一种差不多）
class Solution {
public:
string addBinary(string a, string b) {
int size_a = a.size(), size_b = b.size(), extra = 0;
string res;
while(size_a > 0 || size_b > 0 || extra > 0) {
int i_1 = size_a > 0 ? int(a.at(-1 + size_a--)) - int('0') : 0;
int i_2 = size_b > 0 ? int(b.at(-1 + size_b--)) - int('0') : 0;
int sum = i_1 + i_2 + extra, append = sum % 2;
extra = sum / 2;
res.append(1, char('0' + append));
}
return string(res.rbegin(), res.rend());
}
};
或：
class Solution {
public:
string addBinary(string a, string b) {
int carry = 0;
int pa = a.length() - 1;
int pb = b.length() - 1;
string& res = pa > pb ? a : b;
int p = max(pa, pb);
int tmp;
while ( pa >= 0 && pb >= 0 )
{
tmp = a[pa--] - '0' + b[pb--] - '0' + carry;
res[p--] = (tmp & 1) + '0';
carry = tmp >> 1;
}
while ( p >= 0 )
{
tmp = res[p] - '0' + carry;
res[p--] = (tmp & 1) + '0';
carry = tmp >> 1;
}
if ( carry )
{
res = '1' + res;
}
return res;
}
};