Add Two Numbers - C++ Solution

1. Introduction

This blog post explores a common problem in linked list manipulation: adding two numbers represented by two linked lists. Each node of the lists represents a single digit, and the digits are stored in reverse order. The challenge is to sum these numbers and return the result as a new linked list.

Problem

Given two non-empty linked lists representing two non-negative integers, where each node contains a single digit and the digits are stored in reverse order, the task is to add these two numbers and return the sum as a linked list.

2. Solution Steps

1. Initialize a dummy node to simplify edge cases and a pointer current to build the result list.

2. Iterate through both lists simultaneously, adding corresponding digits.

3. If the sum of two digits is greater than 9, handle the carry over.

4. Continue the process until both lists are fully traversed.

5. If there's a carry left at the end, add a new node for it.

6. Return the next node of the dummy node, which is the head of the result list.

3. Code Program

#include <iostream>
using namespace std;

// Define the ListNode structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to add two numbers represented by linked lists
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* current = &dummy;
    int carry = 0;

    while (l1 || l2 || carry) {
        int sum = carry;
        if (l1) {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2) {
            sum += l2->val;
            l2 = l2->next;
        }

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

    return dummy.next;
}

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

int main() {
    // Creating first number: 342
    ListNode* l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);

    // Creating second number: 465
    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    ListNode* result = addTwoNumbers(l1, l2);
    printLinkedList(result); // Expected Output: 7 -> 0 -> 8
    return 0;
}

Output:

7 -> 0 -> 8

Explanation:

The addTwoNumbers function creates a new linked list to store the sum of the two input numbers. 

It iterates through the input lists, adding corresponding digits and handling the carry. 

A dummy node is used to simplify edge cases, and the function returns the list starting from the dummy node's next pointer. 

The result is a new list representing the sum of the two numbers in reverse order, as demonstrated in the output for the given example.