欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法设计与分析作业题】第一周:2. Add Two Numbers

程序员文章站 2022-03-14 11:01:37
...

题目

【算法设计与分析作业题】第一周:2. Add Two Numbers

C++ solution

/**
 * 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) {
        int carry = 0; // 记录进位
        ListNode* resultList = NULL; // 存储结果List
        ListNode* tempNode = NULL; // 临时节点,用于在结果List中插入新节点
        
        // 加法运算,若其中一个的位数全部加完,补充前导0继续加,直到两个数字的位数全部加完
        while(l1 != NULL || l2 != NULL)
        {
            int val1 = l1 == NULL ? 0 : l1->val;
            int val2 = l2 == NULL ? 0 : l2->val;
            int new_val = val1 + val2 + carry;
            
            // 判断是否进位
            if(new_val > 9)
            {
                carry = 1;
                new_val -= 10;
            }
            else
            {
                carry = 0;
            }
            
            if(resultList == NULL)
            {
                resultList = new ListNode(new_val);
                tempNode = resultList;
            }
            else
            {
                tempNode->next = new ListNode(new_val);
                tempNode = tempNode->next;
            }
            
            l1 = l1 == NULL ? NULL : l1->next;
            l2 = l2 == NULL ? NULL : l2->next;
        }
        
        if(carry == 1)
        {
            tempNode->next = new ListNode(carry);
        }

        return resultList;
    }
};

简要题解

按照加法运算算法,将两个数从低位到高位逐位相加,若和大于或等于10,则向前进位;若其中一个数的位数全部加完,补充前导0继续加,直到两个数的位数全部加完;此时若有进位,则将进位加到运算结果中;运算结束。

相关标签: algorithms