Cover Image for Add two Numbers Represented by Linked Lists in C++
84 views

Add two Numbers Represented by Linked Lists in C++

Adding two numbers represented by linked lists in C++ involves simulating the addition operation as you would do manually, digit by digit, taking care of carrying over values. Here’s a step-by-step implementation:

C++
#include <iostream>

// Definition for singly-linked list.
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 = new ListNode(0); // Create a dummy node to start the result list
    ListNode* current = dummy; // Initialize the current pointer to the dummy node
    int carry = 0; // Initialize the carry value to 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; // Calculate the carry for the next iteration
        current->next = new ListNode(sum % 10); // Add a new node with the remainder to the result
        current = current->next; // Move the current pointer forward
    }

    return dummy->next; // Return the result linked list (skip the dummy node)
}

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

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

    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    std::cout << "Input lists: " << std::endl;
    printList(l1);
    printList(l2);

    ListNode* result = addTwoNumbers(l1, l2);

    std::cout << "Sum of the numbers represented by linked lists: " << std::endl;
    printList(result);

    // Clean up memory
    delete l1;
    delete l2;
    delete result;

    return 0;
}

In this code:

  • We define a ListNode structure to represent a node in the singly-linked list. Each node has an int value and a next pointer to the next node.
  • The addTwoNumbers function takes two linked lists as input and returns a new linked list representing the sum of the two numbers.
  • We use a dummy node to simplify the code and handle the edge case where the result has one more digit than the input lists.
  • We traverse both input lists simultaneously, adding corresponding digits along with any carry from the previous step.
  • We create new nodes for the result as needed and update the current pointer.
  • Finally, we return the result linked list, skipping the dummy node, and clean up memory to prevent memory leaks.

You can customize the main function to create and test other input linked lists as needed.

YOU MAY ALSO LIKE...

The Tech Thunder

The Tech Thunder

The Tech Thunder


COMMENTS