LeetCode #2 - Add Two Numbers

Hello, 👋 Today, we’re going to unravel another interesting problem from LeetCode: “Add Two Numbers” represented as linked lists.

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.

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.

Analysis

The task is to add two numbers represented by two linked lists. Each node in the linked list contains a single digit, and the digits are stored in reverse order.

Input: l1 =  2 -> 4 -> 3 , l2 =  5 -> 6 -> 4
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Approach

The most straightforward approach is to traverse both lists and simulate the addition of two numbers.

Initialize a dummy head of the result list: This dummy head will serve as the starting point of our result linked list.
Initialize carry to 0: The carry will take care of any overflow from the addition of two digits.
Loop through lists while there are still nodes left: On each loop iteration, we add the current digits of the two lists together and set it as the next node of the dummy head.
Handle overflow: If the sum is greater than 9, we set the carry to 1. Otherwise, we set it to 0.
Continue the process: We repeat this process until we’ve gone through both lists.
Handle remaining carry: If there’s still a carry after going through both lists, we add a new node with the digit 1.

Time Complexity

The time complexity for this approach is O(max(m, n)), where m and n are the lengths of the two linked lists. This is because we’re processing all the nodes in both lists once.

Space Complexity

The space complexity is also O(max(m, n)) because the length of the new list is at most max(m, n) + 1.

Code

Here’s the Python and JavaScript code for this approach:

Python

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy_head = ListNode(0)
        p, q, current = l1, l2, dummy_head
        carry = 0
        
        while p is not None or q is not None:
            x = p.val if p is not None else 0
            y = q.val if q is not None else 0
            sum = carry + x + y
            carry = sum // 10
            current.next = ListNode(sum % 10)
            current = current.next
            if p is not None: p = p.next
            if q is not None: q = q.next
        if carry > 0:
            current.next = ListNode(carry)
        return dummy_head.next

JavaScript

var addTwoNumbers = function(l1, l2) {
    let dummyHead = new ListNode(0);
    let p = l1, q = l2, current = dummyHead;
    let carry = 0;

    while (p !== null || q !== null) {
        let x = (p !== null) ? p.val : 0;
        let y = (q !== null) ? q.val : 0;
        let sum = carry + x + y;
        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;
        if (p !== null) p = p.next;
        if (q !== null) q = q.next;
    }
    if (carry > 0) {
        current.next = new ListNode(carry);
    }
    return dummyHead.next;
};

Conclusion

In this post, we tackled the “Add Two Numbers” problem from LeetCode using a straightforward approach. This solution has a time complexity of O(max(m, n)) and a space complexity of O(max(m, n)).

Remember, coding is a journey. Keep exploring, keep learning, and most importantly, have fun doing it!

Happy coding 😄

Learn More:

LeetCode #2 – Add Two Numbers