Add Two Numbers Represented as Linked List in DSA C# - Build from Scratch

Add Two Numbers Represented as Linked List

📖 Scenario: Imagine you have two numbers, but each digit is stored in a linked list node. The digits are stored in reverse order, so the 1's digit is at the head of the list. You want to add these two numbers and get the result as a linked list in the same reversed format.

🎯 Goal: You will create two linked lists representing numbers, then write code to add these two numbers digit by digit, handling carry, and finally print the resulting linked list.

📋 What You'll Learn

Create a linked list node class called ListNode with an integer val and a next pointer.

Create two linked lists representing the numbers 342 and 465 (stored in reverse order).

Create a variable carry to hold the carry during addition.

Write a loop to add corresponding digits of the two lists and carry, creating a new linked list for the sum.

Print the resulting linked list in the format: 7 -> 0 -> 8 -> null.

💡 Why This Matters

🌍 Real World

Adding large numbers digit by digit is useful in calculators, financial software, and systems that handle numbers larger than built-in data types.

💼 Career

Understanding linked lists and how to manipulate them is important for software developers working with data structures, algorithms, and coding interviews.

1

Create the linked list nodes for the first number

Create a class called ListNode with an integer val and a ListNode next. Then create a linked list called l1 representing the number 342 in reverse order: nodes with values 2, 4, and 3 linked together.

DSA C#

// Define ListNode class and create linked list l1 for number 342
// Your code here

Hint

Define the ListNode class with val and next. Then create l1 with nodes 2 -> 4 -> 3.

2

Create the linked list nodes for the second number

Using the ListNode class, create a linked list called l2 representing the number 465 in reverse order: nodes with values 5, 6, and 4 linked together.

DSA C#

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
// Create linked list l2 for number 465
// Your code here

Hint

Create l2 with nodes 5 -> 6 -> 4 to represent 465 reversed.

3

Add the two numbers represented by the linked lists

Create an integer variable called carry and set it to 0. Then write a while loop that continues as long as l1, l2, or carry is not zero. Inside the loop, add the values from l1 and l2 nodes and the carry. Create new nodes for the sum linked list called result starting with a dummy head node. Update carry accordingly.

DSA C#

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

int carry = 0;
// Add the two numbers and create the result linked list
// Your code here

Hint

Use a dummy head node to build the result list. Add digits and carry, update carry, and move pointers.

4

Print the resulting linked list

Write a while loop to print the values of the result linked list nodes separated by ->. After the last node, print null.

DSA C#

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

int carry = 0;
ListNode dummyHead = new ListNode(0);
ListNode current = dummyHead;

while (l1 != null || l2 != null || carry != 0) {
    int val1 = (l1 != null) ? l1.val : 0;
    int val2 = (l2 != null) ? l2.val : 0;
    int sum = val1 + val2 + carry;
    carry = sum / 10;
    current.next = new ListNode(sum % 10);
    current = current.next;
    if (l1 != null) l1 = l1.next;
    if (l2 != null) l2 = l2.next;
}

ListNode result = dummyHead.next;
// Print the result linked list
// Your code here

Hint

Use a loop to print each node's value followed by '->', and print 'null' at the end.

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" mainly involve?

easy

A. Sorting two linked lists in ascending order

B. Adding digits node by node from two linked lists representing numbers

C. Finding the middle node of a linked list

D. Reversing a linked list

Solution

1. Step 1: Understand the problem context

   The problem involves two linked lists where each node contains a single digit. These digits represent numbers in reverse order.

2. Step 2: Identify the required operation

   We need to add these two numbers digit by digit, managing carry, and return the sum as a linked list.

3. Final Answer:

   Adding digits node by node from two linked lists representing numbers -> Option B

4. Quick Check:

   Adding digits node by node = B [OK]

Hint: Focus on digit-wise addition with carry [OK]

Common Mistakes:

• Confusing addition with sorting
• Ignoring carry during addition
• Assuming numbers are stored in forward order

2. Which of the following C# code snippets correctly initializes a linked list node for this problem?

easy

A. ListNode node = new ListNode();

B. ListNode node = ListNode(5);

C. ListNode node = new ListNode(5);

D. ListNode node = new ListNode.val(5);

Solution

1. Step 1: Recall C# object initialization syntax

   In C#, to create an object, use the 'new' keyword followed by the constructor call with parameters.

2. Step 2: Check each option for correct syntax

   A creates node with default val=0, incorrect for val=5. B misses 'new'. C: ListNode node = new ListNode(5); is correct. D has invalid syntax.

3. Final Answer:

   ListNode node = new ListNode(5); -> Option C

4. Quick Check:

   Use 'new' keyword with constructor = C [OK]

Hint: Use 'new' keyword to create objects in C# [OK]

Common Mistakes:

• Omitting 'new' keyword
• Incorrect constructor call syntax
• Trying to assign value directly without constructor

3. What will be the output linked list after adding these two numbers represented as linked lists?

List1: 2 -> 4 -> 3 -> null (represents 342)
List2: 5 -> 6 -> 4 -> null (represents 465)

Code snippet:

var result = AddTwoNumbers(l1, l2);
PrintList(result);

What is the printed linked list?

medium

A. 7 -> 0 -> 8 -> null

B. 8 -> 0 -> 7 -> null

C. 7 -> 10 -> 7 -> null

D. 2 -> 4 -> 3 -> 5 -> 6 -> 4 -> null

Solution

1. Step 1: Add digits node by node with carry

   Adding 2+5=7 (carry 0), 4+6=10 (carry 1), 3+4=7 plus carry 1 = 8.

2. Step 2: Form the resulting linked list

   The result is 7 -> 0 -> 8 -> null, representing 807.

3. Final Answer:

   7 -> 0 -> 8 -> null -> Option A

4. Quick Check:

   342 + 465 = 807 = 7->0->8 [OK]

Hint: Add digits with carry, store result digit-wise [OK]

Common Mistakes:

• Not handling carry correctly
• Appending nodes instead of summing digits
• Confusing order of digits

4. Identify the error in this C# method snippet for adding two numbers represented as linked lists:

public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
    int carry = 0;
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    while (l1 != null || l2 != null) {
        int x = (l1 != null) ? l1.val : 0;
        int y = (l2 != null) ? l2.val : 0;
        int sum = x + y + carry;
        carry = sum / 10;
        current.next = new ListNode(sum % 10);
        current = current.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    return dummy.next;
}

medium

A. Returning dummy instead of dummy.next

B. Incorrect initialization of carry variable

C. Wrong use of ternary operator for x and y

D. Missing check to add carry node after loop ends

Solution

1. Step 1: Analyze loop and carry handling

   The loop adds digits and updates carry, but after loop ends, if carry > 0, it must be added as a new node.

2. Step 2: Identify missing carry node addition

   Code does not add a node for leftover carry after loop, which causes incorrect result for sums like 5+5=10.

3. Final Answer:

   Missing check to add carry node after loop ends -> Option D

4. Quick Check:

   Carry node after loop missing = A [OK]

Hint: Always add leftover carry node after loop [OK]

Common Mistakes:

• Forgetting to add carry node after loop
• Returning dummy instead of dummy.next
• Incorrect carry initialization

5. Given two linked lists representing numbers in reverse order:
List1: 9 -> 9 -> 9 -> 9 -> null (represents 9999)
List2: 1 -> null (represents 1)

What will be the resulting linked list after adding them using the standard algorithm?

hard

A. 0 -> 0 -> 0 -> 0 -> 1 -> null

B. 1 -> 0 -> 0 -> 0 -> 0 -> null

C. 0 -> 0 -> 0 -> 0 -> null

D. 9 -> 9 -> 9 -> 9 -> 1 -> null

Solution

1. Step 1: Add digits with carry step-by-step

   9+1=10 (digit 0, carry 1), then 9+0+1=10 (digit 0, carry 1) repeated for next two nodes.

2. Step 2: Add final carry node

   After last addition, carry is 1, so add new node with value 1 at the end.

3. Final Answer:

   0 -> 0 -> 0 -> 0 -> 1 -> null -> Option A

4. Quick Check:

   9999 + 1 = 10000 = 0->0->0->0->1 [OK]

Hint: Carry can extend list length by one node [OK]

Common Mistakes:

• Ignoring carry after last node
• Appending digits without carry
• Misplacing the carry node