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()函数。