Add Two Numbers
Problem Description
Question
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.
Solve it on LeetCode
Approaches
1. Iterative Approach
The naive approach involves iterating through both linked lists simultaneously, adding the digits, and managing the carry.
Intuition:
- The core idea is to traverse both linked lists while simultaneously keeping track of the carry, resulting from the sum of respective digits.
- When one of the linked lists is exhausted, continue the addition with the remaining linked list considering the carry.
- If we are left with a carry after completely processing both lists, add a new node to represent that carry.
Algorithm:
- Initialize a
dummyHeadwith value0. This will help to easily return the head of the new linked list. - Initialize
currentpointer to point atdummyHead. - Initialize a variable
carryto0. - Loop over the linked lists as long as there are digits to process from either one or there is a carry to consider.
- Compute the sum of the current digits (considering
nullto represent value0) and the carry. - Update the carry based on the sum (it'll be either
0or1). - Create a new node with the digit value of
sum % 10and attach it tocurrent. - Advance to the next nodes in the linked lists as well as move
current. - Return
dummyHead.next.
Code:
Complexity Analysis
- Time Complexity: O(max(m, n)), where
mandnare the lengths of the two lists. We iterate through both lists once. - Space Complexity: O(max(m, n)). The result can be at most max(m, n) + 1 in length to accommodate any carry.