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;
}