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 <= 9Follow up: Could you solve it without reversing the input lists?
In #445 Add Two Numbers II, the digits of two numbers are stored in forward order within linked lists. Since addition normally proceeds from the least significant digit, the challenge is processing the lists from the end without modifying their order directly.
A common and efficient strategy uses two stacks. Traverse both linked lists and push each digit into separate stacks. This allows you to pop digits from the end, simulating reverse traversal. While either stack still has elements (or a carry exists), pop values, compute the sum, and build the result list by inserting nodes at the front.
Another approach is to reverse both linked lists, perform the typical linked list addition (similar to the classic Add Two Numbers problem), and then reverse the result again. Both techniques ensure correct digit alignment and carry handling.
These approaches run in O(n + m) time, where n and m are the lengths of the lists, with additional stack or list manipulation space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based digit processing | O(n + m) | O(n + m) |
| Reverse lists and add | O(n + m) | O(1) extra (excluding output) |
NeetCode
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.
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.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
5}
This Java solution follows a similar pattern: reversing the input lists, adding node values, and managing carry. A dummy node assists in recursively building the final list which is subsequently reversed to present the answer.
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.
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.
1
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
Stack<int> stack1 = new Stack<int>();
Stack<int> stack2 = new Stack<int>();
while (l1 != null) {
stack1.Push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.Push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode result = null;
while (stack1.Count > 0 || stack2.Count > 0 || carry > 0) {
int sum = carry;
if (stack1.Count > 0) sum += stack1.Pop();
if (stack2.Count > 0) sum += stack2.Pop();
carry = sum / 10;
ListNode newNode = new ListNode(sum % 10);
newNode.next = result;
result = newNode;
}
return result;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of linked list addition problems are common in technical interviews at companies like Amazon, Google, and Meta. They test understanding of linked lists, carry propagation, and data structure trade-offs.
A common optimal approach uses two stacks to store digits from both linked lists. This allows processing digits from the least significant side without modifying the original lists. The method runs in O(n + m) time and simplifies carry handling.
Yes, another method is to reverse both linked lists, perform the standard addition used in the original Add Two Numbers problem, and then reverse the resulting list. This avoids extra stack storage but modifies the list structure during computation.
Stacks are particularly useful because the digits are stored in forward order in the linked lists. By pushing nodes onto stacks, you can process digits in reverse order, which aligns with how addition is typically performed.
This C# solution employs System.Collections.Generic.Stack to manage reverse traversal during addition, prepending resulting nodes to form the required output list patiently.