2 Add Two Numbers

题目

2 Add Two Numbers

题解

记输入的数字为\(A(a_m...a_1a_0)\)和\(B(b_n...b_1b_0)\)，进位为\(carry(c_{max(m,n)}...c_1c_0c_{-1})\)，相加的结果为\(Result(r_{max(m,n)+1}...r_1r_0)\)。加法算术的流程为：

1. 对齐A和B的最低位
2. 进位中的\(c_{-1}\)初始化为0，从最低位(i=0)开始进行计算
3. 对当前的第i位，计算\(add= a_i + b_i + c_{i-1}\)
4. 设置\(r_i\)为add的个位部分。若add大于10，则设进位中的\(c_{i}\)为1
5. i增加1，返回第3步进行计算，直到遍历完A和B中的所有位
6. 若最高位的进位(\(c_{max(m,n)}\))为1，则结果的额外最高位(r_{max(m,n)+1)设为1，否则设其为0

复杂度分析 算法只需遍历一次输入的数字，因此时间复杂度为\(O(n)\)。计算的结果最多比输入数字中位数最多的那个多一位，所以空间复杂度也是\(O(n)\)。

代码

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode* result = new ListNode(0);
		ListNode* digit = result;
		bool addUp = false;
		int add = 0;
		do {
			if (l1 != NULL && l2 != NULL) {
				add = l1->val + l2->val;
			}
			if (l1 != NULL && l2 == NULL) {
				add = l1->val;
			}
			if (l1 == NULL && l2 != NULL) {
				add = l2->val;
			}

			if (l1 != NULL) {
				l1 = l1->next;
			}
			if (l2 != NULL) {
				l2 = l2->next;
			}

			if (addUp) {
				add = add + 1;
				addUp = false;
			}
			if (add >= 10) {
				addUp = true;
				add = add % 10;
			}

			digit->val = add;
			if (l1 != NULL || l2 != NULL) {
				digit->next = new ListNode(0);
			} else {
				if (addUp) {
					digit->next = new ListNode(1);
				}
				break;
			}
			digit = digit->next;
		} while (true);
		return result;
	}
};