---
tags: leetcode
---

# [445. Add Two Numbers II](https://leetcode.com/problems/add-two-numbers-ii/)
---
# My Solution
## Solution 1: Reverse the input lists
### The Key Idea for Solving This Coding Question
### C++ Code

/**
 * 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) {}
 * };
 */


struct Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);

        ListNode *dummy = new ListNode(), *it = dummy;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr) {
            int sum = carry;
            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10;
            sum %= 10;
            it->next = new ListNode(sum);
            it = it->next;
        }
        if (carry != 0) {
            it->next = new ListNode(1);
        }

        ListNode *head = dummy->next;
        delete dummy;

        return reverse(head);
    }

private:
    ListNode *reverse(ListNode *head) {
        ListNode *newHead = nullptr;

        while (head != nullptr) {
            ListNode *x = head->next;
            head->next = newHead;
            newHead = head;
            head = x;
        }

        return newHead;
    }
};

### Time Complexity
$O(n1 + n2)$
$n1$ is the number of nodes in `l1`.
$n2$ is the number of nodes in `l2`.
### Space Complexity
$O(max(n1, n2))$
## Solution 2: Without reversing the input lists
### The Key Idea for Solving This Coding Question
### C++ Code

struct Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        int len1 = findLen(l1);
        int len2 = findLen(l2);

        ListNode *it1 = l1, *it2 = l2, *longList;
        int diff;
        if (len1 > len2) {
            diff = len1 - len2;
            longList = l1;
            it1 = adjust(l1, diff);
        } else {
            diff = len2 - len1;
            longList = l2;
            it2 = adjust(l2, len2 - len1);
        }

        ListNode *dummy = new ListNode(), *curr = dummy;
        while (diff > 0) {
            curr->next = new ListNode(longList->val);
            --diff;
            longList = longList->next;
            curr = curr->next;
        }


        while (it1 != nullptr || it2 != nullptr) {
            int sum = 0;
            if (it1 != nullptr) {
                sum += it1->val;
                it1 = it1->next;
            }
            if (it2 != nullptr) {
                sum += it2->val;
                it2= it2->next;
            }

            curr->next = new ListNode(sum);
            curr = curr->next;
        }

        ListNode *head = dummy->next;
        delete dummy;

        head = reverse(head);
        int carry = 0;
        ListNode *prev = nullptr;
        curr = head;
        while (curr != nullptr) {
            curr->val += carry;
            carry = curr->val / 10;
            curr->val %= 10;
            prev = curr;
            curr = curr->next;
        }
        if (carry != 0) {
            prev->next = new ListNode(1);
        }

        head = reverse(head);
        return head;
    }

private:
    int findLen(ListNode *head) {
        int len = 0;
        for (ListNode *it = head; it != nullptr; it = it->next) {
            ++len;
        }
        return len;
    }

    ListNode *adjust(ListNode *head, int diff) {
        while (diff > 0) {
            head = head->next;
            --diff;
        }
        return head;
    }

    ListNode *reverse(ListNode *head) {
        ListNode *newHead = nullptr;

        while (head != nullptr) {
            ListNode *x = head->next;
            head->next = newHead;
            newHead = head;
            head = x;
        }
        return newHead;
    }
};

### Time Complexity
$O(n1 + n2)$
$n1$ is the number of nodes in `l1`.
$n2$ is the number of nodes in `l2`.
### Space Complexity
$O(max(n1, n2))$
# Miscellaneous
<!--
# Test Cases

[7,2,4,3]
[5,6,4]

[2,4,3]
[5,6,4]

[0]
[0]

[9]
[1]

[3,9,9,9,9,9,9,9,9,9]
[7]

[2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9]
[5,6,4,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9,9,9,9]

-->