LeetCode #2:Add Two Numbers(两数相加)

题目描述

类似于大数加法,只不过是以链表的形式给出两个数,模拟手工加法一位一位相加。如果对加法器比较熟悉就知道本质上这就是实现一个十进制的加法器,一位一位加得出本位和进位,注意一些特殊情况。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        int jw = 0;
        ListNode* res = new ListNode(0);
        ListNode* p = res;

        while(l1 != NULL && l2 != NULL) {
            int sum = (l1->val + l2->val + jw) % 10; //本位
            ListNode* q = new ListNode(sum);
            p->next = q;
            p = p->next;
            if(l1->val + l2->val + jw >= 10) //生成进位
                jw = 1;
            else
                jw = 0;
            
            l1 = l1->next;
            l2 = l2->next;
        }

        if(l1 == NULL && l2 == NULL && jw == 1) { //处理最高位遗留进位的情况
            ListNode* q = new ListNode(1);
            p->next = q;
            p = p->next;
        }

        while(l1 != NULL) {
            int sum = (l1->val + jw) % 10; //本位
            ListNode* q = new ListNode(sum); //生成进位
            p->next = q;
            p = p->next;
            if(l1->val + jw >= 10)
                jw = 1;
            else
                jw = 0;

            l1 = l1->next;
            if(l1 == NULL && jw == 1) { //处理最高位遗留进位的情况
                ListNode* q = new ListNode(1);
                p->next = q;
                p = p->next;
            }    
        }

        while(l2 != NULL) {
            int sum = (l2->val + jw) % 10; //本位
            ListNode* q = new ListNode(sum); //生成进位
            p->next = q;
            p = p->next;
            if(l2->val + jw >= 10)
                jw = 1;
            else
                jw = 0;
            
            l2 = l2->next;
            if(l2 == NULL && jw == 1) { //处理最高位遗留进位的情况
                ListNode* q = new ListNode(1);
                p->next = q;
                p = p->next;
            }
        }

        return res->next;
    }
};

发表评论

您的电子邮箱地址不会被公开。