Add Two Numbers这个题目是：把两个整型的数字用两个链表表示，然后把这两个数字相加，最后的结果仍然用链表表示。这个题目能很好的体现一个人对于这种算法题的解题思路，是很好的一个题目。
这个题目很需要算法设计的那四个步骤：
1.设计算法，通过举例子、画图、划分子问题（分治或DP）等方法。
2.设计测试用例
3.编写代码实现
4.对代码进行Debug
所以下面说一下具体的过程：
1.设计算法
这个题目传进来的两个头指针是可以随便移动的，没必要在另外设置两个head指针，直接移动头指针就可以了。
产生的新的链表需要一个头结点，一个当前结点指针。
注意两个数相加的进位，就可以了。最后return头结点的next。
2.测试用例
1.一个链表是NULL，则返回另一个链表就可以了。 2.两个链表不是一般长，长的那个多余的部分直接挂在结果链表的后面，但是注意进位。例如18+249999，最后要增加一个结点 3.两个链表一样长，但是最高位有进位，所以要在malloc一个新的结点，例如345+789
3.代码实现
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode *result = NULL;
ListNode *cur = NULL;
int carry = 0;
ListNode dummy(-1);
result = &dummy;
cur = result;
if(l1 == NULL)
{
result = l2;
return result;
}
if(l2 == NULL)
{
result = l1;
return result;
}
while(l1 != NULL || l2 != NULL)
{
int val1 = l1 == NULL ? 0 : l1->val;
int val2 = l2 == NULL ? 0 : l2->val;
int sum = val1 + val2 + carry;
ListNode *tmp = NULL;
tmp = (ListNode*)malloc(sizeof(ListNode));
tmp->val = sum % 10;
carry = sum / 10;
tmp->next = NULL;
cur->next = tmp;
cur = cur->next;
tmp = NULL;
if(l1 != NULL)
l1 = l1->next;
if(l2 != NULL)
l2 = l2->next;
}
if(carry == 1)
{
ListNode *tmp = (ListNode*)malloc(sizeof(ListNode));
tmp->val = 1;
tmp->next = NULL;
cur->next = tmp;
cur = cur->next;
tmp = NULL;
}
return result->next;
}
4.Debug测试代码。
总结：
对于同时处理两个链表，有两种方法：
1.同时循环两个链表，如果任何一个结束了，就停止循环。然后单独处理剩下的那部分的链表的结点。
2.同时循环两个链表，直到最长的那个循环结束才停止循环，短的那个不够的部分补充合适的数字，比如0或者其他的值。
本题用到的就是第二种的方法。
对于题目中的这种思路就是，按最长的那个链表循环，短的那个链表补上合适的值，0或者其他的值。和上面的这个问题相似的问题就是：
二进制数字的加法，例如a=“11”，b=“1”，那么最后的结果c=“100”。首先加法运算的低位置在字符串的高位置，所以字符串要首先逆序一下。还有就是C++的string和vector有类似的函数来操作这个string。
string addBinary(string a, string b)
{
string c;
int carry = 0;
int alen = a.size();
int blen = b.size();
int len = alen > blen ? alen : blen;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int i = 0;
while(i < len)
{
int avalue = i >= alen ? 0 : (a[i]-'0');
int bvalue = i >= blen ? 0 : (b[i]-'0');
int cvalue = (avalue + bvalue + carry) % 2;
carry = (avalue + bvalue + carry) / 2;
c.insert(c.begin(), cvalue + '0');
i++;
}
if(carry == 1)
{
c.insert(c.begin(), '1');
}
return c;
}
注意reverse函数和sort函数都在#include <algorithm>头文件中，string有begin()和end()函数，然后就是insert()函数。