LeetCode Problem 2 - Add Two Numbers

 

Problem Statement:

LeetCode Problem: "Add Two Numbers"

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zeros, except the number 0 itself.

Function Signature:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2);

Optimal Approach:

The most efficient way to solve this problem is to simulate the addition process similar to how addition is done by hand. Since the digits are stored in reverse order, we start from the least significant digit (head of the list) and proceed to the more significant digits (next nodes). We maintain a carry variable to handle sums greater than 9, which should carry over to the next digit.

Key Idea:

• Traverse both linked lists from the head (least significant digit) to the tail.
• For each pair of digits, add them along with the carry from the previous operation.
• If the sum exceeds 9, calculate the new carry (sum / 10) and store the current digit (sum % 10).
• Continue the process until both lists are fully traversed.
• If there's a remaining carry after the traversal, append it as the last node.

This approach runs in O(n) time, where n is the length of the longer list, and uses O(n) space for the result.

LeetCode-Compatible Code Implementations:

C++ Solution:

#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0); // A dummy node to simplify list creation
        ListNode *current = dummy;
        int carry = 0;
        
        // Traverse both linked lists
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int sum = carry;
            
            // Add values from l1 and l2 if present
            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }
            
            // Calculate carry for next iteration and current digit
            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
        }
        
        return dummy->next; // Return the next node of dummy to exclude dummy node
    }
};

Step-by-Step Explanation of Code:

1. Initialize a dummy node:

   • The dummy node helps simplify edge cases, such as the first addition or when there's a carry remaining at the end. The current pointer points to this dummy node to build the result list.

2. Iterate over both lists:

   • We traverse both linked lists l1 and l2 simultaneously, and for each pair of digits, we add them along with the carry from the previous step.

3. Handle the carry:

   • For each addition, if the sum exceeds 9, we store the remainder (sum % 10) as the current node's value, and calculate the carry (sum / 10) to be used in the next iteration.

4. Create a new node:

   • For each sum, we create a new node with the current digit and attach it to the result list.

5. Return the result:

   • Once both lists are traversed, we return dummy->next, which points to the head of the resultant list, excluding the dummy node.

Dry Run / Execution Steps:

Let's perform a dry run on the input l1 = [2, 4, 3] and l2 = [5, 6, 4]:

• Step 1: Initialize carry = 0, dummy = 0, current = dummy.
• Step 2: Add digits:
  • First iteration: sum = 0 + 2 + 5 = 7 (no carry). Create a node with value 7.
  • Second iteration: sum = 0 + 4 + 6 = 10 (carry 1). Create a node with value 0.
  • Third iteration: sum = 1 + 3 + 4 = 8 (no carry). Create a node with value 8.
• Step 3: No more digits to process, but carry = 0.
• Step 4: The result is [7, 0, 8].

Alternative Approaches & Why Not?

1. Brute Force:

   • Approach: Convert both linked lists to numbers, add the numbers, and convert the result back to a linked list.
   • Time Complexity: O(n), where n is the length of the longest list.
   • Space Complexity: O(n) for storing the numbers.
   • Why Not: This approach works but is less efficient in terms of space and loses the "linked list" problem nature.

2. Sorting:

   • Approach: Sorting both lists (though unnecessary) to ensure they are in the correct order.
   • Time Complexity: O(n log n), where n is the number of nodes in the longer list.
   • Why Not: Sorting adds unnecessary complexity when direct addition works fine.

3. Recursive Approach:

   • Approach: Recursively add nodes from both lists.
   • Time Complexity: O(n), but it can hit stack depth limitations with large lists.
   • Why Not: Iterative approaches are simpler and avoid recursion depth issues.

Best Solution & Why It’s Best:

The iterative approach using a dummy node and a carry variable is the most efficient because:

• Time Complexity: O(n), where n is the length of the longer list.
• Space Complexity: O(n) for the resulting linked list.
• It handles carry propagation efficiently and avoids complications like recursion depth.

Approach	Time Complexity	Space Complexity
Brute Force	O(n)	O(n)
Iterative (Best)	O(n)	O(n)
Recursive	O(n)	O(n)
Sorting	O(n log n)	O(n)

Complexity Analysis:

• Iterative Approach:
  • Time Complexity: O(n) — We traverse the lists once.
  • Space Complexity: O(n) — We store the result in a new linked list.

Conclusion:

The best approach for this problem is the iterative approach with a dummy node, as it efficiently handles carry propagation and is simple to implement. It works in linear time and uses linear space for the result.

Similar Problems for Practice:

1. Add Two Numbers II
2. Reverse Linked List
3. Linked List Cycle

By solving these problems, you can practice linked list manipulation and improve your algorithmic skills.