Add Two Numbers Represented as Linked List in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Adding Two Numbers in Linked List Form

What is the output linked list after adding the two numbers represented by these linked lists?

List 1: 2 -> 4 -> 3 -> null
List 2: 5 -> 6 -> 4 -> null

Each node contains a single digit and the digits are stored in reverse order.

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;
    }
}

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

// Adding 342 + 465 = 807, reversed list: 7 -> 0 -> 8 -> null

A 8 -> 0 -> 7 -> null

B 7 -> 0 -> 8 -> null

C 5 -> 0 -> 7 -> null

D 7 -> 1 -> 7 -> null

💡 Hint

Add digits node by node, remember to carry over if sum is 10 or more.

The two numbers are 342 and 465. Adding them gives 807. Since the digits are stored in reverse, the output list is 7 -> 0 -> 8 -> null.

❓ Predict Output

intermediate

Output When Lists Have Different Lengths

What is the output linked list after adding these two numbers?

List 1: 9 -> 9 -> 9 -> 9 -> null
List 2: 1 -> null

Digits are stored in reverse order.

DSA C#

// Adding 9999 + 1 = 10000, reversed list: 0 -> 0 -> 0 -> 0 -> 1 -> null

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

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

C 0 -> 0 -> 0 -> 1 -> null

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

💡 Hint

Remember to continue adding even if one list ends, and handle carry properly.

9999 + 1 = 10000. The reversed linked list is 0 -> 0 -> 0 -> 0 -> 1 -> null.

🔧 Debug

advanced

Identify the Bug in the Addition Code

What error will this code produce when adding two linked lists?

Code snippet:

while (p != null && q != null) {
    int sum = p.val + q.val + carry;
    carry = sum / 10;
    curr.next = new ListNode(sum % 10);
    curr = curr.next;
    p = p.next;
    q = q.next;
}
// Missing code to handle remaining nodes or carry

A The code will miss adding remaining nodes if lists have different lengths, resulting in incomplete sum.

B The code will cause a NullReferenceException immediately.

C The code will produce an infinite loop.

D The code will correctly add the numbers without errors.

💡 Hint

Check what happens after the while loop ends.

The loop only runs while both lists have nodes. If one list is longer, those nodes are ignored, so the sum is incomplete.

❓ Predict Output

advanced

Output When Result Has Extra Carry Node

What is the output linked list after adding these two numbers?

List 1: 5 -> 6 -> 4 -> null
List 2: 5 -> 4 -> 5 -> null

Digits stored in reverse order.

DSA C#

// Adding 465 + 545 = 1010, reversed list: 0 -> 1 -> 0 -> 1 -> null

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

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

C 0 -> 1 -> 0 -> 1 -> null

D 0 -> 1 -> 1 -> null

💡 Hint

Don't forget to add the carry node at the end if carry > 0.

465 + 545 = 1010. The reversed list is 0 -> 1 -> 0 -> 1 -> null.

🧠 Conceptual

expert

Why Use a Dummy Head Node in Addition of Linked Lists?

Why is a dummy head node commonly used when adding two numbers represented as linked lists?

A It prevents memory leaks by managing node allocation automatically.

B It improves the speed of addition by reducing the number of operations.

C It is required to store the carry value during addition.

D It simplifies code by avoiding special cases for the head node and allows easy return of the result list.

💡 Hint

Think about how linked lists are built node by node.

A dummy head node acts as a fixed starting point, so we don't need to check if the head is null or not when adding nodes. This makes the code cleaner and easier to manage.

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