/*
 * p q 分别指向两个链表的头部
 * 遍历，相加，用bit存储进位，相加需要先加上进位
 * new一个dummy来存储和的位
 */

#include <iostream>
#include <vector>
using namespace std;

struct node{
    int val;
    node* next;
    node(int _val):val(_val),next(nullptr) {}
};

node* nodeListSum(node* list1, node* list2){

    // p q 分别指向两个链表的头部
    auto p = list1;
    auto q = list2;
    // 和链表
    auto dummy = new node(-1);
    auto r = dummy;

    bool bit = 0;
    while(p && q){

        // 两节点之和 + 上一次进位
        int sum = p->val + q->val + bit;
        // 进位
        bit = sum/10;
        int rest = sum%10;

        // 和节点
        r->next = new node(rest);

        p = p->next;
        q = q->next;
        r = r->next;
    }
    // 链表1的剩余节点
    while(p){
        int sum  = p->val + bit;
        bit = sum/10;
        int rest = sum%10;
        r->next = new node(rest);
        p = p->next;
        r = r->next;
    }
    // 链表2的剩余节点
    while(q){
        int sum = q->val + bit;
        bit = sum/10;
        int rest = sum%10;
        r->next = new node(rest);
        q = q->next;
        r = r->next;
    }

    // 最后剩余的进位
    if(bit) r->next = new node(bit);

    auto t = dummy->next;
    delete dummy;
    return t;

}

int main(){

    // 构建两个链表
    vector<int> nums1{9,9,9,9,9,9,9};
    vector<int> nums2{9,9,9,9};

    node* list1_dummy = new node(-1);
    node* list2_dummy = new node(-1);
    node* p = list1_dummy;
    node* q = list2_dummy;

    for(int x : nums1){
        p->next = new node(x);
        p = p->next;
    }
    for(int x : nums2){
        q->next = new node(x);
        q = q->next;
    }

    node* list1 = list1_dummy->next;
    delete list1_dummy;
    node* list2 = list2_dummy->next;
    delete list2_dummy;

    // 求和
    auto res = nodeListSum(list1, list2);
    auto t = res;

    // 输出
    while(t){
        cout<<t->val<<" ";
        t = t->next;
    }
    cout<<endl;

    return 0;
}