Add Two Numbers Represented as Linked List in DSA C#

Mental Model

Each linked list holds a number in reverse order, and we add digit by digit like elementary addition with carry.

Analogy: Imagine adding two numbers on paper from right to left, carrying over when sum exceeds 9, but here each digit is a node in a chain.

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

Dry Run Walkthrough

Input: list1: 2->4->3, list2: 5->6->4 (representing 342 + 465)

Goal: Add the two numbers and return the sum as a linked list in reverse order

Step 1: Add first nodes: 2 + 5 = 7, no carry

Result: 7 -> null

Why: Start adding from least significant digit

Step 2: Add second nodes: 4 + 6 = 10, carry 1

Result: 7 -> 0 -> null

Why: Sum exceeds 9, so store 0 and carry 1

Step 3: Add third nodes plus carry: 3 + 4 + 1 = 8, no carry

Result: 7 -> 0 -> 8 -> null

Why: Add last digits and carry to get final digit

Result:

7 -> 0 -> 8 -> null (represents 807)

Annotated Code

DSA C#

using System;

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

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            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; // advance current to next node
            if (l1 != null) l1 = l1.next; // advance l1
            if (l2 != null) l2 = l2.next; // advance l2
        }
        return dummyHead.next;
    }

    public static void PrintList(ListNode node) {
        while (node != null) {
            Console.Write(node.val);
            if (node.next != null) Console.Write(" -> ");
            node = node.next;
        }
        Console.WriteLine(" -> null");
    }

    public static void Main() {
        ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
        ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
        Solution sol = new Solution();
        ListNode result = sol.AddTwoNumbers(l1, l2);
        PrintList(result);
    }
}

while (l1 != null || l2 != null || carry != 0) {

continue adding while there are digits or carry

int x = (l1 != null) ? l1.val : 0;

get current digit from l1 or 0 if none

int y = (l2 != null) ? l2.val : 0;

get current digit from l2 or 0 if none

int sum = x + y + carry;

sum digits plus carry

carry = sum / 10;

update carry for next digit

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

create new node with digit value

current = current.next;

advance current pointer to new node

if (l1 != null) l1 = l1.next;

advance l1 pointer

if (l2 != null) l2 = l2.next;

advance l2 pointer

Output

7 -> 0 -> 8 -> null

Complexity Analysis

Time: O(max(m, n)) because we traverse both lists once where m and n are their lengths

Space: O(max(m, n)) for the output list that holds the sum digits

vs Alternative: Adding numbers by converting to integers and back is limited by integer size and less efficient; this method works for arbitrarily large numbers.

Edge Cases

One list is empty

Returns the other list as the sum

DSA C#

int x = (l1 != null) ? l1.val : 0;

Sum results in an extra carry digit

Adds an extra node for the carry at the end

DSA C#

while (l1 != null || l2 != null || carry != 0) {

Lists of different lengths

Continues adding digits treating missing nodes as zero

DSA C#

int x = (l1 != null) ? l1.val : 0;

When to Use This Pattern

When you see two linked lists representing numbers in reverse order and need to add them digit by digit, use this pattern to simulate addition with carry.

Common Mistakes

Mistake: Not handling carry after the last nodes are processed
Fix: Include carry in the while loop condition to add extra node if needed

Mistake: Advancing pointers before using their values
Fix: Use current node values before moving pointers forward

Summary

Adds two numbers represented as reversed linked lists digit by digit with carry.

Use when adding large numbers stored as linked lists where direct integer conversion is not feasible.

The key insight is to simulate manual addition from least significant digit with carry propagation.

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