算法设计与分析第一周作业

本次为第一次在leetcode网站上写作业，因此选择中等(medium)难度的题目进行解答。

---

题目简要

使用两个链表模拟两个数进行相加，其中低位在链表头，如数123在链表中表示为3->2->1。

解析

• 该问题的算法与手写加法一致，把两个数当前位以及上一位的进位相加得到结果的当前位的数值，如果该数大于或等于10则有进位，每一位的相加只考虑两个加数的当前位和进位而不需要考虑其他位的加法。

• 有以下几种情况：

1. 表示两个加数的任一个链表为空，则结果为空；

2. 两个加数的位数一样，则各位相加（考虑进位），最后得到结果；

3. 两个加数的位数不一样，则从低位开始相加（考虑进位），直到某一个链表遍历完全，和的剩下的各位数值等于另一个加数的未进行加法运算的各位。  

代码及其解释

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
 		// if one node is null, return
        if (l1 == NULL || l2 == NULL) {
        	return NULL;
        }
        ListNode *result = NULL;
        ListNode *currNode = NULL;
        ListNode *tmp1 = l1;
        ListNode *tmp2 = l2;
        int num1 = 0, num2 = 0, carry = 0;

        while (tmp1 != NULL || tmp2 != NULL) {
        	num1 = (tmp1 == NULL) ? 0 : tmp1->val;
        	num2 = (tmp2 == NULL) ? 0 : tmp2->val;

        	// get the sum of all numbers, with carry 0 at the biginning. 
        	int sum = num1 + num2 + carry;
        	// get the carry
        	carry = sum / 10;
        	// if the list of result is null
        	if (result == NULL) {
        		result = new ListNode(sum % 10);
        		currNode = result;
        	}
        	else {
        		currNode->next = new ListNode(sum % 10);
        		currNode = currNode->next;
        	}

        	if (tmp1 != NULL) tmp1 = tmp1->next;
        	if (tmp2 != NULL) tmp2 = tmp2->next;
        }
        // if the carry is not 0, the result should have one node more
        if (carry > 0) {
        	currNode->next = new ListNode(carry);
        }

        return result;
    }
};

使用currNode来表示进行加法运算的结果的当前位，carry为进位数值。

注意：

1. 用来表示结果的result指针初始值需为NULL，否则代码段第31行的判断会永远为false，切会导致36行的currNode指针的非法访问；
2. 进位carry初始值为0；
3. 每次相加需注意上一位的进位；
4. 循环结束后需要检查是否还有进位。

题目链接