Add Two Numbers Problem and Solution

1. Introduction

The "Add Two Numbers" problem involves adding two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. The task is to return their sum as a linked list.

2. Solution in C++

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *head = new ListNode(0);
    ListNode *node = head;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
        carry = sum / 10;
        node->next = new ListNode(sum % 10);
        node = node->next;
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }
    return head->next;
}

// Function to print the linked list
void printList(ListNode *head) {
    while (head) {
        cout << head->val;
        head = head->next;
    }
    cout << endl;
}

// Example usage
int main() {
    // Create first list: 2 -> 4 -> 3
    ListNode *l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);

    // Create second list: 5 -> 6 -> 4
    ListNode *l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    // Add the two numbers
    ListNode *result = addTwoNumbers(l1, l2);

    // Print the result
    printList(result);
}

Output:

708

Explanation:

1. The function addTwoNumbers takes two linked lists (l1, l2).

2. A dummy head node is created to simplify edge cases.

3. Iterate through both lists, summing up corresponding digits along with the carry.

4. If the sum is ≥ 10, set carry to 1 for the next iteration.

5. Add the remainder of the sum divided by 10 as a new node.

6. Continue until both lists are exhausted and no carry is left.

7. Return the next node of the dummy head, which is the start of the sum list.

3. Solution in Java

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

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

    // Function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            head = head.next;
        }
        System.out.println();
    }

    // Example usage
    public static void main(String[] args) {
        // Create first list: 2 -> 4 -> 3
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        // Create second list: 5 -> 6 -> 4
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        // Add the two numbers
        ListNode result = addTwoNumbers(l1, l2);

        // Print the result
        printList(result);
    }
}

Output:

708

Explanation:

1. The method addTwoNumbers adds two numbers represented by linked lists.

2. A dummy head is used to handle edge cases easily.

3. Iterate through the lists, adding corresponding values along with the carry.

4. If the sum is 10 or more, carry is set for the next addition.

5. The remainder of the sum divided by 10 is added as a new node to the result list.

6. The loop continues until both lists and the carry are processed.

7. Return the list starting from dummy head's next node as the result.

4. Solution in Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)
    current, carry = dummy, 0

    while l1 or l2 or carry:
        val1 = (l1.val if l1 else 0)
        val2 = (l2.val if l2 else 0)
        carry, out = divmod(val1 + val2 + carry, 10)

        current.next = ListNode(out)
        current = current.next

        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy.next

# Function to print the linked list
def printList(head):
    while head:
        print(head.val, end='')
        head = head.next
    print()

# Example usage
if __name__ == "__main__":
    # Create first list: 2 -> 4 -> 3
    l1 = ListNode(2)
    l1.next = ListNode(4)
    l1.next.next = ListNode(3)

    # Create second list: 5 -> 6 -> 4
    l2 = ListNode(5)
    l2.next = ListNode(6)
    l2.next.next = ListNode(4)

    # Add the two numbers
    result = addTwoNumbers(l1, l2)

    # Print the result
    printList(result)

Output:

708

Explanation:

1. The function addTwoNumbers adds two numbers represented by linked lists.

2. A dummy node is created for simplicity in handling edge cases.

3. The loop continues until both lists are processed and there is no carry.

4. Sum each pair of nodes and the carry. Use divmod to get the new digit and carry.

5. The sum's remainder is added as a new node to the result list.

6. Advance each list and the current node.

7. Return the list starting from the dummy node's next as the result.