题解 | #牛群的能量值# 模拟进位加法

知识点

链表 模拟

思路

链表形式的模拟进位的大整数加法, 维护一个进位值carry

由加法的进位我们可以知道下一次的carry值是由上一次的k除以10得到的, 当前位置的值是 k % 10

• 当两个链表都没到达末尾, k值由上一次剩下的carry + l1->val + l2->val组成
• l1到达末尾, l2没到达末尾, k值由上一次剩下的carry + l2->val组成
• l2到达末尾, l1没到达末尾, k值由上一次剩下的carry + l1->val组成 (和上一条不会同时出现)
• l1 l2均到达末尾, k值由carry组成
• l1 l2 到达末尾, carry为0, 循环结束

时间复杂度

只遍历了链表若干次 

AC code (C++)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    ListNode* addEnergyValues(ListNode* l1, ListNode* l2) {
        // 模拟进位加法
        auto dummy = new ListNode(0);
        auto p = dummy;
        int carry = 0;
        while (l1 and l2) {
            int k = l1->val + l2->val + carry;
            p->next = new ListNode(k % 10);
            p = p->next, l1 = l1->next, l2 = l2->next;
            carry = k / 10;
        }
        while (l1) {
            int k = l1->val + carry;
            p->next = new ListNode(k % 10);
            p = p->next, l1 = l1->next;
            carry = k / 10;
        }
        while (l2) {
            int k = l2->val + carry;
            p->next = new ListNode(k % 10);
            p = p->next, l2 = l2->next;
            carry = k / 10;
        }
        while (carry) {
            p->next = new ListNode(carry % 10);
            p = p->next;
            carry /= 10;
        }
        return dummy->next;
    }
};