Add Two Numbers

Problem Link

Problem Statement

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 the sum as a linked list.

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

Examples

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
The input numbers do not contain any leading zero, except 0 itself.

Intuition

Since the digits are stored in reverse order, we can simulate the digit-wise addition like elementary school arithmetic:

Traverse both lists together.
At each step, sum the current digits and the carry.
Add the result's digit to the new list, and update the carry.

Approach

Initialize a dummy node and a temp pointer to build the result list.
Use two pointers curr1 and curr2 to iterate over l1 and l2.
At each step:
- Extract the digits (use 0 if the list has ended).
- Compute the sum and carry.
- Append the digit to the result.
After traversal, if any carry remains, append it as a new node.

Java Code

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;
        ListNode curr1 = l1;
        ListNode curr2 = l2;
        int carry = 0;
        
        while (curr1 != null || curr2 != null) {
            int val1 = (curr1 != null) ? curr1.val : 0;
            int val2 = (curr2 != null) ? curr2.val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            temp.next = new ListNode(sum % 10);
            temp = temp.next;
            if (curr1 != null) curr1 = curr1.next;
            if (curr2 != null) curr2 = curr2.next;
        }
        
        if (carry > 0) {
            temp.next = new ListNode(carry);
        }
        
        return dummy.next;
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	O(max(m, n))
Space Complexity	O(max(m, n))
Explanation	We create a new list with one node per digit

Dry Run

Input:

l1 = [2, 4, 3]  → represents 342
l2 = [5, 6, 4]  → represents 465

Steps:

2 + 5 + 0 = 7 → new node = 7, carry = 0
4 + 6 + 0 = 10 → new node = 0, carry = 1
3 + 4 + 1 = 8 → new node = 8, carry = 0

Output: [7, 0, 8] → represents 807

Conclusion

This problem simulates elementary digit-wise addition of numbers stored in reverse order using linked lists. It’s a classic introduction to linked list arithmetic and pointer manipulation.