Add Two Numbers Represented by Linked Lists in C++

This C++ program adds two numbers where each number is represented as a linked list. The digits are stored in reverse order: the head of each list represents the least significant digit of the number.

Program Code

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Function to add two numbers
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummyHead = new ListNode(0);
    ListNode* current = dummyHead;
    int carry = 0;

    while (l1 != NULL || l2 != NULL || carry) {
        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 dummyHead->next;
}

// Helper function to print the linked list
void printList(ListNode* node) {
    while (node != NULL) {
        std::cout << node->val << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

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

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

    ListNode* result = addTwoNumbers(l1, l2);

    std::cout << "Sum List: ";
    printList(result);

    return 0;
}

Explanation of the Code

The program defines a ListNode structure for the linked list node. It uses a function addTwoNumbers to add the numbers represented by two linked lists. The function traverses both lists simultaneously, adds corresponding digits along with any carry from the previous digit, and stores the result in a new linked list. The carry for each addition is computed as the sum divided by 10, and the digit is stored as the sum modulo 10.

A dummy head node is used to simplify the handling of the head of the result list, avoiding special cases for the head node. After processing both input lists and any remaining carry, the function returns the next node of the dummy head, which is the actual start of the result list.

Conclusion

This C++ program effectively adds two numbers represented as linked lists using basic arithmetic operations and linked list manipulations. It handles numbers of different lengths and possible carry-over values seamlessly.