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:
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:
[1, 100].0 <= Node.val <= 9
Follow up: Could you solve it without reversing the input lists?
This approach involves reversing both linked lists to align the least significant digits and performing the addition operation similarly to how you would add numbers on paper. After the sum is calculated, the result is reversed to restore the original order.
This solution first reverses both input lists to facilitate adding from the least significant to the most significant digit. We traverse both lists, compute the sum for corresponding nodes, and keep track of any carry forward. The resulting linked list is constructed by prepending nodes. Finally, the resultant list is reversed to represent the correct number.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m) where n and m are the lengths of the two linked lists. We reverse both lists and then traverse them. Space Complexity: O(1) if we exclude the space required for the output list.
Another efficient way to solve this problem is using stacks to store digits of both the numbers. This helps to access the least significant digits last, similar to reversing. This allows easier management of carry as we traverse backward effectively without modifying input lists explicitly.
In C, we use two stacks to hold digits of the linked lists. As we pop elements from the stacks, we calculate the sum, manage the carry, and construct the resultant list by prepending nodes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n and m are the lengths of linked lists. Space Complexity: O(n + m), for storing numbers in stacks.
| Approach | Complexity |
|---|---|
| Using Reversal of Linked Lists | Time Complexity: O(n + m) where n and m are the lengths of the two linked lists. We reverse both lists and then traverse them. Space Complexity: O(1) if we exclude the space required for the output list. |
| Using Stack Data Structure | Time Complexity: O(n + m), where n and m are the lengths of linked lists. Space Complexity: O(n + m), for storing numbers in stacks. |
Add Two Numbers - Leetcode 2 - Python • NeetCode • 293,331 views views
Watch 9 more video solutions →Practice Add Two Numbers II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor