【leetcode】 算法题2 两数相加

 

问题

 　

  

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

 

代码实现

 　 

 

#include <vector>

#include <map>

#include <iostream>

#include <math.h>

/**

*

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

*/

using namespace std;

struct ListNode{

    int val;

    ListNode *next;

    ListNode(int x) : val(x), next(NULL){}

};

template<class T>

int length(T& arr) {

    return sizeof(arr)/ sizeof(arr[0]);

}

class Solution {

public:

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        uint64_t carry = 0, sum = 0;

        ListNode prehead(0), *p = &prehead;

        while (l1 || l2) {

            sum =  (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;

            sum = carry / 10;

            p->next  = new ListNode(sum % 10);

            l1 = l1 ? l1->next : l1;

            l2 = l2 ? l2->next : l2;

            p = p->next;

        }

        return prehead.next;

    }

};

int main(int argc, char** argv){

    int a[] = {2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9};

    ListNode* tmp = new ListNode(0);

    ListNode* ptr1 = tmp;

    for (int i = 0; i < length(a); i++) {

        ptr1->next = new ListNode(a[i]);

        ptr1 = ptr1->next;

    }

    ptr1 = tmp->next;

    delete tmp;

    tmp = new ListNode(0);

    int b[] = {5,6,4,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9,9,9,9};

    ListNode* ptr2 = tmp;

    for (int j = 0; j < length(b); j ++) {

        ptr2->next = new ListNode(b[j]);

        ptr2 = ptr2->next;

    }

    ptr2 = tmp->next;

    delete tmp;

    Solution* solution = new Solution();

    solution->addTwoNumbers(ptr1, ptr2);

    delete solution;

    return 0;

}

　　

 

推荐