Leetcode 2. Add Two Numbers

Problem Explanation

The problem is basically asking to add up two non-negative numbers which are represented in a reversed linked list format and return the result as a reversed linked list. The linked lists represent the numbers with each node containing one digit, and the digits are in reverse order; meaning the head of the linked list will represent the least significant digit, and the tail will represent the most significant digit.

Let's illustrate this with an example. The linked list (2 -> 4 -> 3) represents the number 342 and the linked list (5 -> 6 -> 4) represents the number 465. The problem wants us to get the sum 342 + 465 = 807, and represent that sum as a linked list in the form: 7 → 0 → 8.

Solution Approach

The approach is to iterate from left to right through each linked list simulating the addition of digits from two numbers. We start with a dummy node whose next node is the start of our resulting list. As we iterate through the two input lists, we add the corresponding digits from each list together (along with any carry from the previous addition), save the one's digit in the result list, and carry the ten's digit (if any) over to the next sum. We proceed in this way until we exhaust both input lists. At the end, if a carry remains, we add a new node to our result list with the remaining carry.

Python Solution

1
2python
3class Solution:
4    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
5        dummy = ListNode(0)
6        curr = dummy
7        carry = 0
8        
9        while l1 or l2 or carry:
10            if l1:
11                carry += l1.val
12                l1 = l1.next
13            if l2:
14                carry += l2.val
15                l2 = l2.next
16            curr.next = ListNode(carry % 10)
17            carry //= 10
18            curr = curr.next
19            
20        return dummy.next

Java Solution

1
2java
3public class Solution {
4    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
5        ListNode dummy = new ListNode(0);
6        ListNode curr = dummy;
7        int carry = 0;
8        
9        while (l1 != null || l2 != null || carry != 0) {
10            if (l1 != null) {
11                carry += l1.val;
12                l1 = l1.next;
13            }
14            if (l2 != null) {
15                carry += l2.val;
16                l2 = l2.next;
17            }
18            curr.next = new ListNode(carry % 10);
19            carry /= 10;
20            curr = curr.next;
21        }
22
23        return dummy.next;
24    }
25}

JavaScript Solution

1
2javascript
3var addTwoNumbers = function(l1, l2) {
4    let dummy = new ListNode(0);
5    let curr = dummy;
6    let carry = 0;
7    
8    while (l1 !== null || l2 !== null || carry !== 0) {
9        if (l1 !== null) {
10            carry += l1.val;
11            l1 = l1.next;
12        }
13        if (l2 !== null) {
14            carry += l2.val;
15            l2 = l2.next;
16        }
17        curr.next = new ListNode(carry % 10);
18        carry = Math.floor(carry / 10);
19        curr = curr.next;
20    }
21    
22    return dummy.next;
23};

C++ Solution

1
2cpp
3class Solution {
4public:
5    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
6        ListNode dummy(0);
7        ListNode* curr = &dummy;
8        int carry = 0;
9
10        while (l1 != nullptr || l2 != nullptr || carry != 0) {
11            if (l1 != nullptr) {
12                carry += l1->val;
13                l1 = l1->next;
14            }
15            if (l2 != nullptr) {
16                carry += l2->val;
17                l2 = l2->next;
18            }
19            curr->next = new ListNode(carry % 10);
20            carry /= 10;
21            curr = curr->next;
22        }
23
24        return dummy.next;
25    }
26};

C# Solution

1
2csharp
3public class Solution {
4    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
5        ListNode dummy = new ListNode(0);
6        ListNode curr = dummy;
7        int carry = 0;
8
9        while (l1 != null || l2 != null || carry != 0) {
10            if (l1 != null) {
11                carry += l1.val;
12                l1 = l1.next;
13            }
14            if (l2 != null) {
15                carry += l2.val;
16                l2 = l2.next;
17            }
18            curr.next = new ListNode(carry % 10);
19            carry /= 10;
20            curr = curr.next;
21        }
22
23        return dummy.next;
24    }
25}

Problem Complexity Analysis

The complexity for all the programming language solutions to this problem, assuming n as the maximum length of two lists, are:

Time complexity

The time complexity is O(n) because in the worst-case scenario we need to iterate through each node in both lists once. This happens when the lengths of the provided lists are equal.

Space complexity

The space complexity is also O(n) considering a scenario where each addition results in a carry. In the worst-case scenario, the final list created is n+1 nodes long, which is linearly proportional to n.

Conclusion

This problem focuses on handling linked lists and simulating the addition process as performed on paper, including managing the "carry" from one digit to the next. Solving this problem helps in strengthening skills with basic arithmetic, linked-lists and the concept of carrying in addition. The solution has been provided in multiple programming languages which are Python, Java, JavaScript, C++, and C# enabling the programmer to understand and solve the problem in a language they are comfortable with.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫