[LeetCode] 2. Add Two Numbers

链接

描述

有两个代表非负整数的非空单链表，链表的每一个结点代表一个十进制位，反向存储的。把这两个数字相加，并反其结果。

提示

除了数值 0 以外，不用考虑有前导 0 的情况。

举例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8

思路

由于十进制位是逆序保存在链表中的，所以顺序遍历链表正好得到个位、十位、百位……，正好方便从低位开始相加。唯一需要注意的就是高位不存在的情况。题目本身是很简单的。

代码

/**
 * 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) {
        ListNode* phead = NULL;
        ListNode* prev = NULL;
        bool carry = false;

        for(;;){
            int sum = int(carry);
            if(l1) sum += l1->val;
            if(l2) sum += l2->val;
        
            carry = sum >= 10;
            if(carry) sum -= 10;
        
            ListNode* pcur = new ListNode(sum);
            if(prev == NULL){
                prev = pcur;
                phead = pcur;
            }
            else{
                prev->next = pcur;
                prev = pcur;
            }
        
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        
            if(!l1 && !l2){
                break;
            }
        }

        if(carry){
            ListNode* pa = new ListNode(1);
            prev->next = pa;
            pa->next = NULL;
            prev = pa;
        } 

        prev->next= NULL;
        return phead;
    }
};