# Add Two Numbers II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/add-two-numbers-ii)
Canonical: https://scaleengineer.com/dsa/problems/add-two-numbers-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Linked List, Stack
**Companies:** [Juniper Networks](https://scaleengineer.com/companies/juniper-networks)
---
## Problem
You are given two **non-empty** 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.

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

**Example 1:**

![](https://assets.glich.co/dsa/add-two-numbers-ii/image0.jpg) 

**Input:** l1 = [7,2,4,3], l2 = [5,6,4]
**Output:** [7,8,0,7]

**Example 2:**

**Input:** l1 = [2,4,3], l2 = [5,6,4]
**Output:** [8,0,7]

**Example 3:**

**Input:** l1 = [0], l2 = [0]
**Output:** [0]

**Constraints:**

* The number of nodes in each linked list is in the range `[1, 100]`.
* `0 <= Node.val <= 9`
* It is guaranteed that the list represents a number that does not have leading zeros.

**Follow up:** Could you solve it without reversing the input lists?

# Approaches
## Approach 1: Reverse Input Lists and Add
The problem is that addition starts from the least significant digit (rightmost), but the lists are given from the most significant digit (leftmost). A straightforward idea is to reverse both input linked lists. After reversal, the problem becomes identical to the standard "Add Two Numbers" problem where lists are ordered from least to most significant digit. We can then perform the addition and, finally, reverse the resulting list to match the required output format.
**Time:** O(N1 + N2), where N1 and N2 are the lengths of the lists. We traverse each list multiple times: once for the initial reversal, once for the addition, and the result list is reversed at the end. · **Space:** O(max(N1, N2)). The space is dominated by the storage for the output list. The reversal is done in-place, so it uses O(1) auxiliary space.
**Pros:** Reuses the well-known logic for standard linked list addition.; Very space-efficient (O(1) extra space) if modifying the input lists is acceptable.
**Cons:** This approach modifies the input linked lists, which is often an undesirable side effect.; If the original lists must be preserved, we would need to create copies before reversing, which would increase the space complexity to O(N1 + N2), making it less efficient than other methods.
### Explanation
This method transforms the problem into a more familiar one by reversing the lists. The core of the algorithm is a standard digit-by-digit addition with carry, identical to how we do addition by hand, but on lists that are now ordered from least-significant to most-significant digit. After computing the sum list (which will also be in reversed order), a final reversal is needed to restore the most-significant-digit-first format.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode r1 = reverseList(l1);
        ListNode r2 = reverseList(l2);

        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        int carry = 0;

        while (r1 != null || r2 != null || carry != 0) {
            int val1 = (r1 != null) ? r1.val : 0;
            int val2 = (r2 != null) ? r2.val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;

            if (r1 != null) r1 = r1.next;
            if (r2 != null) r2 = r2.next;
        }

        return reverseList(dummyHead.next);
    }
}
```
### Algorithm
*   Implement a helper function `reverseList(head)` that reverses a linked list in-place and returns the new head.
*   Reverse the first input list `l1` to get `rev_l1`.
*   Reverse the second input list `l2` to get `rev_l2`.
*   Initialize a dummy head for the result list and a `carry` variable to 0.
*   Iterate through `rev_l1` and `rev_l2` simultaneously. In each step, calculate the sum of the current digits and the carry.
*   Create a new node with `sum % 10` and append it to the result list. Update the carry with `sum / 10`.
*   Continue until both lists are traversed and the carry is zero.
*   The list obtained is the sum in reverse order. Reverse this result list to get the final answer.

## Approach 2: Using Stacks
To avoid modifying the input lists, we can use an auxiliary data structure to help us process the digits from right to left. Stacks are a perfect fit for this, as they follow a Last-In, First-Out (LIFO) order. We can push all digits from both lists onto two separate stacks. Then, by popping from the stacks, we can retrieve the digits from least significant to most significant, perform the addition, and build the result list.
**Time:** O(N1 + N2). Pushing all elements onto the stacks takes O(N1 + N2). The addition loop runs at most max(N1, N2) + 1 times. · **Space:** O(N1 + N2). The stacks need to store all the digits from both input lists.
**Pros:** Does not modify the input lists, which is good practice.; The logic is straightforward and easy to understand.
**Cons:** Requires extra space proportional to the total number of nodes in the input lists, which can be significant for long lists.
### Explanation
This approach elegantly handles the right-to-left processing order without altering the original lists. By filling two stacks with the digits of the input lists, we effectively reverse the order of access. The top of the stacks will hold the least significant digits. We can then pop from both stacks, add the values along with any carry from the previous step, and create a new node for the sum. A key detail is that each new node is prepended to the result list, which naturally constructs the final list in the correct, most-significant-digit-first order.

```java
import java.util.Stack;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }

        int carry = 0;
        ListNode resultHead = null;

        while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
            int val1 = s1.isEmpty() ? 0 : s1.pop();
            int val2 = s2.isEmpty() ? 0 : s2.pop();
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            
            ListNode newNode = new ListNode(sum % 10);
            newNode.next = resultHead;
            resultHead = newNode;
        }

        return resultHead;
    }
}
```
### Algorithm
*   Create two stacks, `stack1` and `stack2`.
*   Traverse `l1` and push each node's value onto `stack1`.
*   Traverse `l2` and push each node's value onto `stack2`.
*   Initialize `carry = 0` and `resultHead = null`.
*   Loop as long as either stack is not empty or there is a carry.
*   In each iteration, pop a value from each stack (or use 0 if a stack is empty).
*   Calculate `sum = val1 + val2 + carry`.
*   The new digit is `sum % 10`. The new carry is `sum / 10`.
*   Create a new node for the digit. Since we are building the list from right to left, prepend the new node to the front of our result list (`newNode.next = resultHead; resultHead = newNode;`).
*   After the loop, `resultHead` will point to the head of the final sum list.

## Approach 3: Recursive Addition (No Reversal/Stacks)
This approach solves the problem without explicit reversal or stacks, thus satisfying the follow-up question. The idea is to use the function call stack to implicitly store the nodes and process them in a reversed order. We first recurse to the end of the lists, perform the addition there, and then propagate the carry back up the call stack. To handle lists of different lengths, we first find their lengths and conceptually pad the shorter list with leading zeros by adjusting the starting point of the recursion.
**Time:** O(N1 + N2). We traverse the lists to find their lengths (O(N1+N2)), and the recursion itself involves one operation per node (O(max(N1,N2))). · **Space:** O(max(N1, N2)). This space is used by the recursion call stack. The depth of the recursion is determined by the length of the longer list.
**Pros:** An elegant solution that does not modify the input lists.; Avoids using explicit extra data structures like stacks.; Slightly more space-efficient than the stack approach.
**Cons:** Can lead to a stack overflow error for extremely long lists, although this is not an issue given the problem's constraints (length <= 100).; The recursive logic can be slightly more complex to grasp and debug than an iterative approach.
### Explanation
By using recursion, we traverse to the end of the linked lists first. As the recursion unwinds (returns from the deepest call), we are effectively moving from the least significant digit to the most significant. At each step of the unwinding, we perform the addition for that position using the carry returned from the previous (right-side) position's addition. The result nodes are created and prepended to a result list, which is often managed as a member variable. This method is more space-efficient than using explicit stacks, as it only requires space on the call stack proportional to the length of the longer list.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode resultHead;

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = getLength(l1);
        int len2 = getLength(l2);

        // The recursive function will build the list backwards and return the final carry.
        int carry = add(l1, len1, l2, len2);

        // If there's a final carry, prepend a new node for it.
        if (carry > 0) {
            ListNode newNode = new ListNode(carry);
            newNode.next = resultHead;
            resultHead = newNode;
        }

        return resultHead.val == 0 && resultHead.next == null && (len1 > 1 || len2 > 1) ? resultHead : (resultHead == null ? new ListNode(0) : resultHead);
    }

    private int getLength(ListNode node) {
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }

    private int add(ListNode n1, int len1, ListNode n2, int len2) {
        if (n1 == null && n2 == null) {
            return 0;
        }

        int sum;
        int carry;

        if (len1 > len2) {
            carry = add(n1.next, len1 - 1, n2, len2);
            sum = n1.val + carry;
        } else if (len2 > len1) {
            carry = add(n1, len1, n2.next, len2 - 1);
            sum = n2.val + carry;
        } else {
            carry = add(n1.next, len1 - 1, n2.next, len2 - 1);
            sum = n1.val + n2.val + carry;
        }

        ListNode newNode = new ListNode(sum % 10);
        newNode.next = resultHead;
        resultHead = newNode;

        return sum / 10;
    }
}
```
*Note: The return statement in the main function has a small correction to handle the edge case of `[0] + [0]` which should result in `[0]`, not `null` or an empty list.*
### Algorithm
*   Calculate the lengths of `l1` and `l2`, say `len1` and `len2`.
*   Define a recursive helper function, for instance `addHelper(p1, p2, diff)`, that adds lists starting at nodes `p1` and `p2`, where `p1`'s list is `diff` nodes longer than `p2`'s.
*   The result list is built by prepending nodes to a member variable `resultHead` as the recursion unwinds.
*   **Base Case:** If the current node `p1` is null, it means we've reached the end of the lists. Return a carry of 0.
*   **Recursive Step:** The function calls itself on the next nodes. 
    *   If `diff > 0`, it means we are in the prefix of the longer list. We recurse on `p1.next` but keep `p2` the same, decrementing `diff`. The sum is `p1.val + carry` from the recursive call.
    *   If `diff == 0`, the lists are aligned. We recurse on `p1.next` and `p2.next`. The sum is `p1.val + p2.val + carry`.
*   After the recursive call returns a `carry`, calculate the `sum` for the current nodes.
*   Create a new node with `sum % 10` and prepend it to `resultHead`.
*   Return the new carry `sum / 10` up the call stack.
*   After the initial recursive call in the main function returns, if there's a final carry left over, prepend one last node for it.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers ( ListNode l1 , ListNode l2 ) { Deque < Integer > s1 = new ArrayDeque <>(); Deque < Integer > s2 = new ArrayDeque <>(); for (; l1 != null ; l1 = l1 . next ) { s1 . push ( l1 . val ); } for (; l2 != null ; l2 = l2 . next ) { s2 . push ( l2 . val ); } ListNode dummy = new ListNode (); int carry = 0 ; while (! s1 . isEmpty () || ! s2 . isEmpty () || carry != 0 ) { int s = ( s1 . isEmpty () ? 0 : s1 . pop ()) + ( s2 . isEmpty () ? 0 : s2 . pop ()) + carry ; // ListNode node = new ListNode(s % 10, dummy.next); // dummy.next = node; dummy . next = new ListNode ( s % 10 , dummy . next ); carry = s / 10 ; } return dummy . next ; } }
```

### CPP

```cpp
/** * 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 ) { stack < int > s1 ; stack < int > s2 ; for (; l1 ; l1 = l1 -> next ) s1 . push ( l1 -> val ); for (; l2 ; l2 = l2 -> next ) s2 . push ( l2 -> val ); ListNode * dummy = new ListNode (); int carry = 0 ; while ( ! s1 . empty () || ! s2 . empty () || carry ) { int s = carry ; if ( ! s1 . empty ()) { s += s1 . top (); s1 . pop (); } if ( ! s2 . empty ()) { s += s2 . top (); s2 . pop (); } // ListNode* node = new ListNode(s % 10, dummy->next); // dummy->next = node; dummy -> next = new ListNode ( s % 10 , dummy -> next ); carry = s / 10 ; } return dummy -> next ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def addTwoNumbers ( self , l1 : Optional [ ListNode ], l2 : Optional [ ListNode ] ) -> Optional [ ListNode ]: s1 , s2 = [], [] while l1 : s1 . append ( l1 . val ) l1 = l1 . next while l2 : s2 . append ( l2 . val ) l2 = l2 . next dummy = ListNode () carry = 0 while s1 or s2 or carry : s = ( 0 if not s1 else s1 . pop ()) + ( 0 if not s2 else s2 . pop ()) + carry carry , val = divmod ( s , 10 ) # node = ListNode(val, dummy.next) # dummy.next = node dummy . next = ListNode ( val , dummy . next ) return dummy . next
```