02.Add Two Numbers

📘 LeetCode 2: Add Two Numbers

📌 Problem Overview

• Problem Number: 2
• Problem Name: Add Two Numbers
• Difficulty: Medium
• Category: Linked List
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the Linked List algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/2.Add-Two-Numbers/:

// [2,4,3]
// [5,6,4]
// [0]
// [0]
// [9,9,9,9,9,9,9]
// [9,9,9,9]
// ListNode result = AddTwoNumbers(new ListNode(1, new ListNode(2, null)), new ListNode(1, new ListNode(2, null)));
ListNode result = AddTwoNumbers(new(2, new(8)), new(9, new(7)));
// ListNode result = AddTwoNumbers(new(2, new(4, new(3))), new(5, new(6, new(4))));
Print(result);
// You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
// You may assume the two numbers do not contain any leading zero, except the number 0 itself.
void Print(ListNode node)
{
    while (node != null)
    {
        System.Console.Write(node.val);
        node = node.next;
    }
}
 
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 val1 = l1 != null ? l1.val : 0;
        int val2 = l2 != null ? l2.val : 0;
 
        int sum = carry + val1 + val2;
 
        carry = sum / 10;
        int digit = sum % 10;
        current.next = new ListNode(digit);
        current = current.next; 
        l1 = l1?.next;
        l2 = l2?.next;
    }
    return dummyHead.next; 
}
 
class ListNode
{
    public ListNode next { get; set; }
    public int val { get; set; }
 
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.