Solving the "Add Two Numbers" Problem in LeetCode using C#

Posted on 10/06/2023 by Jacob R Phillips

#csharp #linked-list #nodes #pointers

This classic problem, often tagged as a linked list problem, is an excellent opportunity to enhance your algorithmic skills.

Here is my video on how to solve the Add Two Numbers problem:

Welcome to another exciting programming tutorial! Today, we'll dive deep into solving the "Add Two Numbers" problem on LeetCode using C#. This classic problem, often tagged as a linked list problem, is an excellent opportunity to enhance your algorithmic skills. By the end of this tutorial, you'll have a clear understanding of how to approach similar problems and write efficient code.

Let's embark on this coding journey!

Problem Description:

The "Add Two Numbers" problem on LeetCode presents us with two non-empty linked lists that represent two non-negative integers. The digits are stored in reverse order, with each node containing a single digit. Our task is to add the two numbers and return the result as a linked list.

For example, given the following two linked lists:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Understanding the Solution:

Before diving into the code, let's understand some key concepts and the high-level steps of the solution:

1. Sentinel Node (Dummy Node):

The dummy node is a sentinel node that simplifies the code by providing a consistent starting point for the result linked list. It ensures the result list is never null and simplifies insertions.

2. Pointer Setup:

We initialize pointers, p and q, to the head of the input linked lists l1 and l2. These pointers will help us traverse the linked lists while maintaining references to the original head nodes.

3. Carryover:

The carry variable keeps track of any carryover when adding digits. It is crucial for handling cases where the sum of two digits is greater than or equal to 10.

Solving the Problem:

To solve this problem efficiently, we'll create a C# function that simulates the process of adding two numbers digit by digit while keeping track of any carryovers. Here's a high-level overview of the steps:

1. Initialize a dummy node and two pointers to the head of the input linked lists.

2. Initialize variables for the current sum, carryover, and the result linked list.

3. Traverse both linked lists simultaneously, adding the corresponding digits along with any carryovers.

4. If the sum of two digits is greater than or equal to 10, set the carryover to 1; otherwise, set it to 0.

5. Create a new node with the sum modulo 10 and add it to the result linked list.

6. Move the pointers to the next nodes in the input lists.

7. Repeat steps 3-6 until both input lists are exhausted.

8. If there's a remaining carryover, add it as a new node in the result list.

9. Return the result linked list.

Let's implement this algorithm in C#.

public class Solution 
{
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) 
    {
        //dummy node
        ListNode sentinel = new ListNode(0);

        //pointers
        ListNode p = l1;
        ListNode q = l2;
        ListNode current = sentinel;

        //carryover
        int carry = 0;

        //Manually iterate over both linked lists
        while(p != null || q != null)
        {
            //extracted values from nodes into value1 & value2
            int value1 = (p != null) ? p.val : 0;
            int value2 = (q != null) ? q.val : 0;

            //Add extracted values and carry together
            int sum = carry + value1 + value2;

            //isolate tens position
            carry = sum / 10;

            //capture and store ones position in new node
            current.next = new ListNode(sum % 10);

            //Increment current position
            current = current.next;

            //Increment list pointers
            if(p != null)
            {
                p = p.next;
            }

            if(q != null)
            {
                q = q.next;
            }
        }

        //if carry > 0, created new node with it's value to that of carry
        if(carry > 0)
        {
            current.next = new ListNode(carry);
        }

        //return new linked list without the dummy node
        return sentinel.next;
    }
}

Conclusion:

And there you have it! We've successfully solved the "Add Two Numbers" problem on LeetCode using C#. I hope this tutorial has been helpful in understanding the problem and implementing an efficient solution.

Remember, practice makes perfect in algorithmic problem-solving, so don't hesitate to tackle similar problems on LeetCode to sharpen your skills.

Thank you for reading, and happy coding!