<p>You are given two <strong>non-empty</strong> linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/09/sumii-linked-list.jpg" style="width: 523px; height: 342px;" />
<pre>
<strong>Input:</strong> l1 = [7,2,4,3], l2 = [5,6,4]
<strong>Output:</strong> [7,8,0,7]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> l1 = [2,4,3], l2 = [5,6,4]
<strong>Output:</strong> [8,0,7]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> l1 = [0], l2 = [0]
<strong>Output:</strong> [0]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in each linked list is in the range <code>[1, 100]</code>.</li>
	<li><code>0 &lt;= Node.val &lt;= 9</code></li>
	<li>It is guaranteed that the list represents a number that does not have leading zeros.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong>&nbsp;Could you solve it without reversing the input lists?</p>

class Solution {
public:
    vector<int> vec_con(ListNode* l) {
        vector<int> v1;
        ListNode* curr = l;
        while (curr != nullptr) {
            v1.push_back(curr->val);
            curr = curr->next;
        }
        return v1;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> v1 = vec_con(l1);
        vector<int> v2 = vec_con(l2);
        vector<int> v3;

        int n1 = v1.size();
        int n2 = v2.size();
        
        int i = n1 - 1, j = n2 - 1; // Start from the last elements of v1 and v2
        int carry = 0;

        // Add corresponding elements from v1 and v2 and handle carry
        while (i >= 0 || j >= 0 || carry > 0) {
            int x1 = (i >= 0) ? v1[i] : 0; // If i is in bounds, take v1[i], otherwise 0
            int x2 = (j >= 0) ? v2[j] : 0; // If j is in bounds, take v2[j], otherwise 0

            int sum = x1 + x2 + carry;
            carry = sum / 10;
            v3.push_back(sum % 10); // Push the last digit of the sum

            i--; // Decrement indices
            j--;
        }

        // Create a new list from the v3 vector, which now contains the digits of the sum
        ListNode* dummy = new ListNode(0); // Dummy node to simplify list creation
        ListNode* curr = dummy;

        // v3 contains the sum digits in reverse order, so we iterate from back to front
        for (int k = v3.size() - 1; k >= 0; --k) {
            curr->next = new ListNode(v3[k]);
            curr = curr->next;
        }

        return dummy->next; // Return the head of the newly created list
    }
};
78500