Hello coders! Today we will be discussing the solution to the Add Two Numbers LeetCode Problem.
Problem Statement
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 <= 9It is guaranteed that the list represents a number that does not have leading zeros.
Analysis
The question is asking us to add two linked lists together, and each linked list represents an integer that is backwards. So for example, the integer 342 is represented by the linked list 2->4->3. To solve this problem, we're going to follow the same basic addition rules as if we were solving this problem by hand. We start with the least significant digit from the two lists and add them. If the result greater than or equal to 10, we want to carry the 1 and apply the least significant digit from our result to our answer (we can find this using the modulus operator - result % 10). We continue this process until we run out of digits to add.
The trick to this problem is to watch out for null pointer exceptions since we are working with linked lists.
Implementation
1package leetcode.questions;
2
3import leetcode.common.ListNode;
4
5public class AddTwoNumbers {
6
7 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
8 if (l1 == null && l2 == null) {
9 return null;
10 }
11 ListNode dummy = new ListNode(-1);
12 ListNode current = dummy;
13 int carry = 0;
14 while (l1 != null || l2 != null) {
15 int currentSum = 0;
16 if (l1 != null) {
17 currentSum += l1.val;
18 l1 = l1.next;
19 }
20 if (l2 != null) {
21 currentSum += l2.val;
22 l2 = l2.next;
23 }
24 currentSum += carry;
25 if (currentSum > 9) {
26 currentSum = currentSum % 10;
27 carry = 1;
28 }
29 else {
30 carry = 0;
31 }
32 current.next = new ListNode(currentSum);
33 current = current.next;
34 }
35 if (carry == 1) {
36 current.next = new ListNode(1);
37 }
38 return dummy.next;
39 }
40
41}
Before we move onto the space and time complexity of the algorithm, there is an edge case we caught that I would like to point out. On line 35, after we have iterated through both of our linked lists, if carry is equal to one, we need to add a 1 on the end of our answer before returning. This means after adding the most significant digit from our two lists, we got a result greater than or equal to 10 and needed to carry the one. This can happen in the scenario 8 + 8. After adding the two digits, we get 16, so we apply the 6 to our answer and carry the 1. However, both of our pointers will be null after iterating them forward. Since we still have the carry, we need to apply the one to our solution, giving us 6->1, or 16.
Time Complexity
In this problem, we have two inputs representing the two linked lists. If we represent the length of l1 as n, and the length of l2 as m, in the worst case our algorithm above is iterating max(n, m) times. This is because we are looping until both the pointer to l1 and the pointer to l2 are null. Therefore, the time complexity of the algorithm is O(max(n, m)).
Space Complexity
We are storing our result in a new linked list, which is considered an auxiliary data structure. Our resulting linked list is, at most, max(n, m) + 1 in size. The + 1 comes from line 35, where we check if carry is equal to 1. If so, we are adding a new node to our linked list. Therefore, the space complexity of our algorithm is O(max(n, m)).
Conclusion
The Add Two Numbers LeetCode problem can be solved in O(max(n, m)) time and O(max(n, m)) space. At the current time of writing, this solution is 83.14% faster than all Java submissions!
The code can be found on my github - if you found it helpful, please leave the repo a star!