2014
03-20

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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

#include <iostream>
using namespace std;

struct ListNode {
int val;
ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};

class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode * ans = NULL, *last = NULL;
int up = 0;
while (NULL != l1 && NULL != l2) {
int tmp = l1->val + l2->val + up;
up = tmp / 10;
//第一个单独处理
if (NULL == last) {
ans = new ListNode(tmp % 10);
last = ans;
} else
last = pushBack(last, tmp % 10);
l1 = l1->next;
l2 = l2->next;
}
while (NULL != l1) {
int tmp = l1->val + up;
last = pushBack(last, tmp % 10);
up = tmp / 10;
l1 = l1->next;
}
while (NULL != l2) {
int tmp = l2->val + up;
last = pushBack(last, tmp % 10);
up = tmp / 10;
l2 = l2->next;
}
if (0 != up) {
ListNode * l = new ListNode(up);
last->next = l;
}
return ans;
}

//在末尾添加值val，返回链表尾
ListNode * pushBack(ListNode * last, int val) {
ListNode * l = new ListNode(val);
last->next = l;
return l;
}
};

//测试
int main() {
ListNode * ln1 = new ListNode(9);
ListNode * ln2 = new ListNode(9);
ln1->next = ln2;
//ListNode * ln3 = new ListNode(3);
//ln2->next = ln3;
ListNode * n1 = new ListNode(1);
//	ListNode * n2 = new ListNode(6);
//	n1->next = n2;
//	ListNode * n3 = new ListNode(4);
//	n2->next = n3;
Solution s;
ListNode * ans = s.addTwoNumbers(ln1, n1);
while (NULL != ans) {
cout << ans->val << " ";
ans = ans->next;
}
return 0;
}