Add Two Numbers - 每日算法

每日算法——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;    }};