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 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.

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

To add two numbers represented as linked lists, where each node contains a single digit, you can traverse both lists simultaneously and perform the addition digit by digit. Here’s the implementation for adding two numbers:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // Dummy node to hold the result
        ListNode curr = dummy; // Current node for constructing the result list
        int carry = 0; // Variable to store the carry value

        // Traverse both input lists
        while (l1 != null || l2 != null) {
            int val1 = (l1 != null) ? l1.val : 0; // Get the value of the current node in l1 (or 0 if null)
            int val2 = (l2 != null) ? l2.val : 0; // Get the value of the current node in l2 (or 0 if null)

            // Compute the sum of the current digits and the carry value
            int sum = val1 + val2 + carry;
            carry = sum / 10; // Update the carry

            // Create a new node with the resulting digit and add it to the result list
            curr.next = new ListNode(sum % 10);
            curr = curr.next;

            // Move to the next nodes in the input lists
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        // If there is still a carry after traversing both lists, add it as a new node
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return dummy.next; // Return the head of the resulting list
    }
}

In this solution:

1. We create a dummy node to hold the result. We also initialize a curr pointer to keep track of the current node for constructing the result list.
2. We traverse both input lists simultaneously, digit by digit until both lists reach the end.
3. For each pair of digits, we compute the sum and carry value from the previous addition.
4. We create a new node with the resulting digit (sum % 10) and add it to the result list. We update the curr pointer to the new node.
5. If a carry remains after traversing both lists, we add it as a new node.
6. Finally, we return the next node of the dummy node, which represents the head of the resulting list.

This approach allows us to add the numbers efficiently and construct the resulting list in a single pass through the input lists.

Suppose we have two linked lists representing numbers:

List 1: 2 -> 4 -> 3 (represents the number 342)

List 2: 5 -> 6 -> 4 (represents the number 465)

We will add these two numbers together using the provided solution.

1. We start with a dummy node (initialized as 0) and set the curr pointer to the dummy node. We also initialize the carry variable as 0.

Dummy: 0
curr: 0
carry: 0

2. We traverse both input lists simultaneously.
For the first iteration:

• l1 points to the node with value 2 in List 1.
• l2 points to the node with value 5 in List 2.

3. We compute the sum of the current digits and the carry value.

• Sum = 2 + 5 + 0 (carry) = 7
• Carry = Sum / 10 = 7 / 10 = 0 (integer division)

4. We create a new node with the resulting digit (sum % 10 = 7 % 10 = 7) and add it to the result list. We update the curr pointer to the new node.

Dummy: 0 -> 7
curr: 7
carry: 0

5. Move to the next nodes in the input lists.

• l1 moves to the node with value 4 in List 1.
• l2 moves to the node with value 6 in List 2.

6. Repeat the process of computing the sum, creating a new node, and updating pointers.

• Sum = 4 + 6 + 0 (carry) = 10
• Carry = Sum / 10 = 10 / 10 = 1

Dummy: 0 -> 7 -> 0
curr: 0
carry: 1

7. Move to the next nodes in the input lists.

• l1 moves to the node with value 3 in List 1.
• l2 moves to the node with value 4 in List 2.

8. Repeat the process for the final pair of digits.

• Sum = 3 + 4 + 1 (carry) = 8
• Carry = Sum / 10 = 8 / 10 = 0

Dummy: 0 -> 7 -> 0 -> 8
curr: 8
carry: 0

9. Since we have reached the end of both input lists, we check if there is any remaining carry.

• Since the carry is 0, we don’t create a new node.

10. Finally, we return the next node of the dummy node, which represents the head of the resulting list.

Result: 7 -> 0 -> 8

The resulting list represents the sum of the numbers 342 and 465, which is 807.

The solution traverses the input lists digit by digit, computing the sum and carrying values as it goes. It creates a new linked list to represent the sum, and the resulting list represents the addition of the two input numbers.