Description
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.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
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.
Approach
Since it’s a linked list, it’s suitable to use recursion. In each recursion, add the values of the current nodes of the two linked lists and pass the carry to the next recursion.
Solution
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
return addTwoLinkedListWithCarry(l1, l2);
};
function addTwoLinkedListWithCarry(l1, l2, carry = 0) {
// Base case: if both lists are null and there is no carry, return null
if (!l1 && !l2 && !carry) return null;
const sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
// Recursively call the function for the next nodes and carry
const next = addTwoLinkedListWithCarry(
l1?.next,
l2?.next,
Math.floor(sum / 10)
);
return new ListNode(sum % 10, next);
}
Complexity Analysis
Time Complexity
The function addTwoLinkedListWithCarry recursively processes each node until both linked lists are fully traversed. Given the lengths of l1 and l2 are n and m, the maximum number of recursive calls is max(n, m). Thus, the time complexity is O(max(n, m)).
Space Complexity
-
Recursive depth: The depth of the recursion will be at most
max(n, m), which corresponds to the length of the longer linked list. This depth determines the space used on the call stack. -
New nodes: The space used by the new nodes created in the linked list will be at most
max(n, m) + 1, as we create a new node for each digit in the sum, and the extra 1 is for a possible carry at the end.
Thus, the space complexity is O(max(n, m)), due to both the recursive call stack and the new nodes.