#include <iostream>
using namespace std;
 
 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };
 
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
		
		ListNode *l3 = NULL;
		ListNode *l3Tail = NULL;
		int sum = 0;
		int carryFlag = 0;
		int current = 0;
		
		if (l1 == NULL) {
			return l2;
		}
		if (l2 == NULL) {
			return l1;
		}
		
		while (l1 != NULL || l2 != NULL) {
			sum = carryFlag;
			if (l1 != NULL) {
				sum = sum + l1->val;
				l1 = l1->next;
			}
			if (l2 != NULL) {
				sum = sum + l2->val;
				l2 = l2->next;
			}
			carryFlag = sum / 10;
			current = sum % 10;
			
			ListNode * temp = new ListNode(current);
			temp->next = NULL;
			if(l3 == NULL) {
				l3 = temp;
				l3Tail = temp;
			} else {
				l3Tail->next = temp;
				l3Tail = l3Tail->next;
			}			
		}
		
		if (carryFlag != 0) {
			ListNode *temp = new ListNode(carryFlag);
			temp->next = NULL;
			l3Tail->next = temp;
			l3Tail = l3Tail->next;	
		}
		
		return l3;
    }
    
    ListNode *initLinkList(int array[], int length) {
		ListNode *head = NULL;
		ListNode *tail = NULL; 
		int i =0 ;
		for(i = 0; i < length; i++) {
			ListNode * temp = new ListNode(array[i]);
		//	temp->val = array[i];
		//	temp->next = NULL;
			if(i == 0) {
				head = temp;
				tail = temp;
			} else {
				tail->next = temp;
				tail = tail -> next;
			}
		//	cout<<"tail->val:"<<tail->val<<endl;
		}
		
		return head;
    }
    
    void print(ListNode *link) {
    	ListNode *tail = NULL;
    	tail = link;
		while(tail){			
    		cout<<tail->val;
			if (tail->next) {
				cout<<"->";
			}
			tail = tail->next;	
    	}
    	cout<<endl;
    }

};

int main(){
	Solution solution;
	
	int array1[3]={2, 4, 3};
	int array2[4]={5, 6, 7,8};
//	ListNode *L1;
//	ListNode *L2;
	ListNode *L1 = solution.initLinkList(array1, 3);
	ListNode *L2 = solution.initLinkList(array2, 4);
	
	solution.print(L1);
	solution.print(L2);
	
	ListNode *L3 = solution.addTwoNumbers(L1, L2);
	solution.print(L3);
	return 1; 

}