Leetcode Problem 2 - Add Two Numbers

 Add Two Numbers

Difficulty: Medium

Given two non-empty linked lists representing non-negative integers, where the digits are stored in reverse order, return their sum as a linked list.

Each node contains a single digit, and there are no leading zeros, except when the number itself is 0.

---

Example 1:

Input:

l1 = [2,4,3], l2 = [5,6,4]

Output:

[7,0,8]

Explanation:

342 + 465 = 807, and in reverse order, it is [7,0,8].

---

Example 2:

Input:

l1 = [0], l2 = [0]

Output:

[0]

---

Example 3:

Input:

l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

Output:

[8,9,9,9,0,0,0,1]

---

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• Each node's value is between 0 and 9.
• The linked list represents a valid number (no leading zeros).

---

Solution Approach

Algorithm:

1. Create a dummy node to help build the result list.
2. Use a pointer (current) to track the current node.
3. Use a carry variable to handle sums greater than 9.
4. Traverse both linked lists:
   • Compute the sum of the current nodes and carry.
   • Create a new node with the last digit (sum % 10).
   • Update carry (sum / 10).
   • Move to the next nodes.
5. If carry remains at the end, add a new node.
6. Return the next node of the dummy, which is the head of the sum list.

---

Code (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 dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;

            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

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

        return dummy.next;
    }
}

// Example Usage
class Program {
    static void Main() {
        Solution solution = new Solution();

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

        ListNode result = solution.AddTwoNumbers(l1, l2);

        // Print the result
        while (result != null) {
            Console.Write(result.val + " ");
            result = result.next;
        }
    }
}

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Linked List Traversal	O(max(m, n))	O(max(m, n))

• We traverse both linked lists once, making the time complexity O(max(m, n)).
• The space complexity is also O(max(m, n)), as we store the result in a new linked list.

---

Why This Approach?

✅ Handles different list lengths
✅ Manages carry properly
✅ Efficient O(n) solution

This is the most optimal approach to solving the Add Two Numbers problem. 🚀