2 两数之和 c++

LeetCode2 两数之和

问题描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

将这两个数相加起来，返回一个新的链表来表示它们的和。假设除了数字 0 之外，这两个数都不会以 0 开头。

算法思路

从两个链表的表头元素开始逐个相加，设立一个进位标志，直到遍历完两个链表的所有元素且进位标志为0时结束。

即结束的条件为： ! ( L1 || L2 || carry)

代码实现

#include<iostream>

using namespace std;

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

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

int main(){
    ListNode l1(0);
    ListNode l2(0);
    ListNode l3(0);
    ListNode *p1 = &l1;
    ListNode *p2 = &l2;
    ListNode *p3 = &l3;
    p1->val = 9;
    p2->val = 8;
    p3 = addTwoNumbers(p1, p2);
    while(p3 != nullptr){
        cout << p3->val << " ";
        p3 = p3->next;
    }
    cin.get();
    return 0;	//程序执行后输出：7 1
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode vHead(0), *p = &vHead;		//构造一个头结点，并用指针p指向该结点，返回时将头结点的下一个结点返回。
    int carry = 0; 
    while(l1 || l2 || carry){	
        int temp = 0;	//链表的下一个元素的值
        if(l1 != nullptr) temp += l1->val;
        if(l2 != nullptr) temp += l2->val;
        temp += carry;

        carry = temp / 10;
        temp %= 10;

        ListNode *next = l1 ? l1 : l2;
        if(next == nullptr) next = new ListNode(temp);
        next->val = temp;

        p->next = next;
        p = p->next;
        l1 = l1 ? l1->next : nullptr;
        l2 = l2 ? l2->next : nullptr;
    }
    return vHead.next;
}