Add Two Numbers Represented as Linked List | Leetcode 2

The LeetCode Problem 2: Add Two Numbers is a classic linked list problem, and it’s a common interview question for testing algorithmic and coding skills. This problem can be solved in multiple ways, starting from a brute force approach to more optimized solutions. In this article, we’ll walk through various solutions, starting from the most basic brute force approach to the most efficient one, all in Java.

Problem Statement of Add Two Numbers problem:

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.

Note:

In real-world applications, numbers can be huge, often surpassing the range of standard data types. Think about financial systems or scientific computations where precise, large number addition is crucial. This problem demonstrates how such operations can be performed using data structures like linked lists, where digits are processed one by one, just like a human might add numbers digit-by-digit from right to left.

Why Reverse Order?
The problem stores numbers in reverse order because it mimics how we add numbers by hand. Starting from the least significant digit (units place) ensures that carry propagation happens naturally during the addition process. This way, we can process digits and carry simultaneously without needing to revisit previous digits.

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 <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Approach 1: Brute Force Approach

The brute force method involves iterating through both linked lists, extracting the values, performing the addition, and manually handling the carry. Though simple, this approach doesn’t handle many edge cases efficiently and is not optimal.

Java Code Implementation (Brute Force):

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class AddTwoNumbersBruteForce {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode result = new ListNode(0);
        ListNode current = result;

        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;

            int sum = carry + x + y;
            carry = sum / 10;

            current.next = new ListNode(sum % 10);
            current = current.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (carry > 0) {
            current.next = new ListNode(carry);
        }

        return result.next;
    }
}

Explanation:

• Iterating Through the Lists: We go through both linked lists at the same time, adding corresponding digits from l1 and l2.
• Handling Carry: If the sum of two digits exceeds 9, we store the remainder in the current node and carry over the quotient to the next node.
• Edge Case: If there’s a carry left after both lists are traversed, we add it to the result list.

Complexity:

• Time Complexity: O(max(m, n)), where m and n are the lengths of the input lists.
• Space Complexity: O(max(m, n)), as we create a new list to store the result.

Approach 2: Recursive Approach

We can also use recursion to solve this problem. In the recursive approach, we dive into each pair of digits, perform the addition, and use recursion to handle the next nodes.

Java Code Implementation (Recursive):

public class AddTwoNumbersRecursive {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addTwoNumbers(l1, l2, 0);
    }

    private ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }

        int sum = carry;
        if (l1 != null) sum += l1.val;
        if (l2 != null) sum += l2.val;

        ListNode resultNode = new ListNode(sum % 10);
        resultNode.next = addTwoNumbers(l1 != null ? l1.next : null, l2 != null ? l2.next : null, sum / 10);

        return resultNode;
    }
}

Explanation:

• Recursive Call: The function addTwoNumbers() calls itself recursively with the next nodes from l1 and l2, along with the carry value.
• Base Case: If both l1 and l2 are null and there’s no carry left, we return null.
• Recursive Processing: We process the current nodes and handle the carry in the recursive call.

Complexity:

• Time Complexity: O(max(m, n)), similar to the brute force approach.
• Space Complexity: O(max(m, n)), but it also includes the call stack for recursion, making it a little less efficient for large inputs.

Approach 3: Optimized Iterative Approach

In the optimized approach, we handle the digits and carry in a single pass without unnecessary checks. This solution is very similar to the brute force approach but avoids redundant operations.

Java Code Implementation (Optimized Iterative):

public class AddTwoNumbersOptimized {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p = l1, q = l2, current = dummy;
        int carry = 0;

        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = 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 dummy.next;
    }
}

Explanation:

• Efficient Sum Calculation: We calculate the sum in one go and only perform necessary operations.
• Handling Nulls Gracefully: Instead of nested checks, we handle null nodes by defaulting their values to 0.
• Avoiding Redundant Operations: This approach removes unnecessary steps seen in brute force solutions.

Complexity:

• Time Complexity: O(max(m, n)) – single pass over the input lists.
• Space Complexity: O(max(m, n)) for storing the result.

Key Edge Cases to Consider

• Unequal Length Lists: One list might be longer than the other, but we handle this by treating missing nodes as 0.
• Carry Handling: A carry may remain after the final digits are summed, so we check for this case and append a new node if necessary.
• Empty Lists: Both lists being empty is a rare but possible edge case, and the solutions handle it by returning 0.

Conclusion

The problem “Add Two Numbers” is a great way to practice working with linked lists and understand carry handling during number addition. We’ve seen various solutions, starting from the brute force to recursive, and finally an optimized iterative approach. The key takeaway is the ability to efficiently traverse and manipulate linked lists in Java, making sure we handle edge cases such as carry-over and unequal length lists.

If you’re preparing for coding interviews or learning Java algorithms, this problem is an excellent exercise in both recursion and iterative techniques for linked list manipulation.