2. Add Two Numbers

• 题目描述：
  

• 题目思路：

这道题目比较简单，一开始我的思路是把两个链表里存储的数变成int类型，然后两个int类型相加，在把加和sum分解成个位，十位，百位，然后把分解之后的数据再插入到链表中即可，所以一开始的代码是这样的：

ListNode* createListNode(int val, struct ListNode* link)
{
//	struct ListNode* tp = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* tp = new ListNode(val);
	tp->next = link;
	return tp;
}

class Solution 
{
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
	{
		int add1 = 0;
		int add2 = 0;
		int i = 0;
		int numresult = 0;
		vector<int> output;
		ListNode* result = NULL;
		if ((l1->val == 0) && (l2->val == 0))
		{
			result = createListNode(0,NULL);
			return result;
		}
		while (1)
		{
			add1 = add1 + l1->val * pow(10,i);
			l1 = l1->next;
			i = i + 1;
			if (l1 == NULL)
			{
				break;
			}
		}
		i = 0;
		while (1)
		{
			add2 = add2 + l2->val * pow(10, i);
			l2 = l2->next;
			i = i + 1;
			if (l2 == NULL)
			{
				break;
			}
		}
		numresult = add1 + add2;
		i = 0;

		while (numresult)
		{
			output.push_back(numresult % 10);
			numresult = numresult / 10;
		}

		result = createListNode(output[output.size() - 1], NULL);

		for (i = output.size() - 2;i >= 0;i--)
		{
			result = createListNode(output[i], result);
		}

		return result;
	}
};

提交之后发现，LeetCode的测试数据是

这样的话，不论是用int类型还是long类型，都是不可能存储这么长的数据，看来这个题目我一开始的思路就不正确。

• 第二次的思路
  在参考了网上的资料之后，将代码修改为如下：
  先声明一个头指针，因为对链表操作唯一的接口就是头指针，然后再声明一个指针cur，这是常用的一种手段，cur指向当前的节点。然后将l1和l2中的val相加，然后申请新的节点，把相加之后的结果（sum % 10）存放到新节点中，此时如果需要进位，将进位标志carry设置为(sum / 10),在结束整个循环之后，如果还需要进位，就再申请新的节点。

class Solution 
{
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
	{
		ListNode* frist = new ListNode(0);
		ListNode* cur = frist;
		int carry = 0;  //保存低位向高位的进位
		int sum = 0;
		while (l1 || l2)
		{
			int add1 = (l1 ? l1->val : 0);
			int add2 = (l2 ? l2->val : 0);
			sum = add1 + add2 + carry;
			cur->next = new ListNode(sum % 10);
			carry = sum / 10;
			cur = cur->next;
			if (l1)
			{
				l1 = l1->next;
			}
			if (l2)
			{
				l2 = l2->next;
			}
		}
		if (carry)
		{
			cur->next = new ListNode(1);
		}
		return frist->next;
	}
	
};