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

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

void createList(ListNode *&L,int arr[],int n)
{
    int i;
    ListNode *p=NULL;
    for(i=0; i<n; i++)
    {
        ListNode *tmp=new ListNode(arr[i]);
        if(L==NULL)
        {
            L=tmp;
            p=tmp;
        }
        else
        {
            p->next=tmp;
            p=tmp;
        }
    }
}

ListNode *merge(ListNode *L1,ListNode *L2)
{
    if(L1==NULL&&L2==NULL)
        return NULL;
    if(L1==NULL||L2==NULL)
        return L1!=NULL?L1:L2;
    ListNode *p=L1;
    ListNode *pre=L1;
    ListNode *q=L2;
    int carry=0;
    while(p&&q)
    {
        int sum=p->val+q->val+carry;
        p->val=sum%10;
        carry=sum/10;
        pre=p;
        p=p->next;
        q=q->next;
    }
    while(p)
    {
        int sum=p->val+carry;
        cout<<sum<<endl;
        p->val=sum%10;
        carry=sum/10;
        pre=p;
        p=p->next;
    }
    ListNode *tmp=NULL;
    while(q)
    {
        int sum=q->val+carry;
        tmp=new ListNode(sum%10);
        carry=sum/10;
        pre->next=tmp;
        pre=tmp;
        q=q->next;
    }
    if(carry==1)
    {
        tmp=new ListNode(carry);
        pre->next=tmp;
    }
    return L1;
}

int main()
{
    ListNode *L1=NULL;
    ListNode *L2=NULL;
    int arr1[3]={7,1,9};
    int arr2[5]={5,9};
    createList(L1,arr1,3);
    createList(L2,arr2,2);
    ListNode *head=merge(L1,L2);
    ListNode *p=head;
    while(p)
    {
        cout<<p->val<<" ";
        p=p->next;
    }
    cout<<endl;
}