每日算法——letcode系列

标签： 算法 C++ LetCode

问题 Add Two Numbers

Difficulty: Medium

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 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) {
        
    }
};

翻译

两链表对应数之和

难度系数：中等

给定两个由正整数组成的链表，数在链表中是倒序存放的，并且每个节点上的数是一位整数。把这两上链表上的数相加并返回一个链表

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

思路

题中为什么说倒序，因为如果(2 -> 4 -> 3)看成一个数应该是243，如果跟(5 -> 6 -> 4)564相加应该得807，但由于是倒序放的，应该先从高位相加。

注意的是，题中没有说两个链表长度相同，我认为应该适应长度不相同的时候，还有就是相加后的链表有可能多一位。

代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr && l1 == nullptr){
            return nullptr;
        }
        
        ListNode* head = nullptr, **temp = &head;
        
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr) {
            int a = getValAndMoveToNext(l1);
            int b = getValAndMoveToNext(l2);
            int newVal = (a + b + carry) % 10;
            carry = (a + b + carry) / 10;
            ListNode* node = new ListNode(newVal);
            *temp = node;
            temp = &node->next;
        }
        
        // 最后当carrry大于0（为1）时，应该进一位
        if (carry > 0){
            ListNode* node = new ListNode(carry);
            *temp = node;
        }
        return head;
    }
    
private:
    int getValAndMoveToNext(ListNode* &l){
        if (l == nullptr){
            return  0;
        }
        
        int x = 0;
        x = l->val;
        l = l->next;
        return  x;
    }
};