00002. Leetcode: Add Two Numbers – Problem and Solution

Introduction to Add Two Numbers Problem

The “Add Two Numbers” leetcode problem is a classic algorithmic challenge frequently encountered in coding interviews. The problem statement goes like this: Given two non-empty linked lists representing two non-negative integers, where each node in the linked list contains a single digit and the digits are stored in reverse order, add the two numbers and return the sum as a linked list. It’s assumed that the two numbers do not contain any leading zeros, except for the number 0 itself.

Example

Input:

l1 = [2,4,3]
l2 = [5,6,4]

Output:

[7,0,8]

Explanation: 342 + 465 = 807.

Constraints

• The number of nodes in each linked list is in the range [1, 100].
• Each node’s value is between 0 and 9.
• It is guaranteed that the list represents a number that does not have leading zeros.

Solution: Simulating Addition with Linked Lists

Problem Analysis

To solve this problem, we need to simulate the process of adding two numbers. Since the digits are stored in reverse order, we can traverse the linked lists simultaneously, adding corresponding digits along with any carry from the previous step. The result is a new linked list representing the sum of the two numbers.

C# Implementation

Here’s the C# implementation of the solution:

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

        while (l1 != null || l2 != null || carry != 0)
        {
            int sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
            carry = sum / 10;

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

            l1 = l1?.next;
            l2 = l2?.next;
        }

        return result.next;
    }
}

Explanation

• We create a result linked list to store the sum.
• We use a current pointer to keep track of the current node in the result linked list.
• We iterate through both input linked lists (l1 and l2) simultaneously, calculating the sum of corresponding digits along with any carry from the previous step.
• We update the result linked list with the current digit of the sum and move the pointers to the next nodes in the input linked lists and the result linked list.

Conclusion

The “Add Two Numbers” problem is an excellent exercise in linked list manipulation and simulating mathematical operations. The solution provides an efficient way to add two numbers represented as linked lists, and the approach can be generalized to similar problems involving linked lists.