#include <bits/stdc++.h>
using namespace std;

// You are given two non-empty linked lists representing two
// non-negative integers. The digits are stored in reverse order, and
// each of their nodes contains a single digit. Add the two numbers
// and return the sum as a linked list.


// You may assume the two numbers do not contain any leading zero,
// except the number 0 itself.


/**
 * Definition for singly-linked list.
 */

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

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* res = new ListNode;

        return res;
    }
};

int main(void)
{
    // head of list and front of vector contain least significant digit
    vector<tuple<vector<int>,vector<int>,vector<int>>> testCases = {
        // L1              L2         expected
        { {1,2,3},         {4,5,6},   {5,7,9} },  // 321 + 654 = 975
        { {2,4,3},         {5,6,4},   {7,0,8} },  // 342 + 465 = 807
        { {9,9,9,9,9,9,9}, {9,9,9,9}, {8,9,9,9,0,0,0,1} },
    };
    
    function<void(ListNode*)> printReverse = [&printReverse](ListNode* node)
    {
        if (node == nullptr)
            return;
        printReverse(node->next);
        cout << node->val << " ";
    };

    function<void(ListNode*)> printForward = [&printForward](ListNode* node)
    {
        if (node == nullptr)
            return;
        cout << node->val << " ";
        printForward(node->next);
    };

    for (auto tc: testCases)
    {
        function<void(ListNode*,vector<int>&)> buildList = [&buildList](ListNode* dummyHead, vector<int>& v)
        {
            ListNode* current = dummyHead;            
            for (auto i: v)
            {            
                current->next = new ListNode(i);
                current = current->next;
            }            
        };
        
        vector<int>& v1 = get<0>(tc);
        cout << "L1: "; for (auto i: v1) { cout << i << " "; } cout << endl;
        ListNode* L1 = new ListNode(v1.back());
        // build list from test case vector back to front
        for (auto iter = next(v1.rbegin()); iter != v1.rend(); iter++)
        {
            L1 = new ListNode(*iter, L1);
        }

        cout << "L1 printForward: ";
        printForward(L1);
        cout << endl;
        
        cout << "L1 printReverse: ";
        printReverse(L1);
        cout << endl;

        vector<int>& v2 = get<1>(tc);
        cout << "L2: "; for (auto i: v2) { cout << i << " "; } cout << endl;
        ListNode* L2 = new ListNode(v2.back());
        // build list from test case vector back to front
        for (auto iter = next(v2.rbegin()); iter != v2.rend(); iter++)
        {
            L2 = new ListNode(*iter, L2);
        }

        cout << "L2 printForward: ";
        printForward(L2);
        cout << endl;
        
        cout << "L2 printReverse: ";
        printReverse(L2);
        cout << endl;

        Solution s;
        ListNode* result = s.addTwoNumbers(L1, L2);
        cout << "result: ";
        printForward(result);
        cout << endl;

        vector<int>& expected = get<2>(tc);
        int width = 10;
        
        cout << setw(width) << "expected: "; for (auto i: expected) { cout << i << " "; } cout << endl;
        cout << "-----------------------\n";        
    }
}