The provided code demonstrates a solution for adding two numbers represented as linked lists in C++. It assumes that the input linked lists depict the numbers in a reversed order, meaning the lowest significant digit is located at the beginning of the list. To begin, a structure is set up to represent the nodes of the linked list, where each node contains an integer value and a reference to the subsequent node in the list. Additionally, there is a function named addTwoNumbers designed to accept two pointers pointing to the heads of the input linked lists and to provide a pointer to the head of the resultant linked list upon execution.
C++ Code
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* curr = 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;
curr->next = new ListNode(sum % 10);
curr = curr->next;
}
return dummy->next;
}
int main() {
// example inputs
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);
// add two linked lists
ListNode* result = addTwoNumbers(l1, l2);
// print the result
while (result) {
cout << result->val << " ";
result = result->next;
}
cout << endl;
return 0;
}
Output
7 0 8
The result id due to formation:
Input:
l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4
Internal Working Output:
7 -> 0 -> 8
This represents the sum 342 + 465 = 807.
Explanation:
The addTwoNumbers function starts by generating a placeholder node to serve as the initial element of the resulting linked list. This placeholder node is set with an initial value of 0 and its next pointer is assigned as NULL. The function establishes a reference pointer named curr that points to this placeholder node. The subsequent step involves traversing through both input linked lists along with any carryover from the previous sum operation. During each iteration, it computes the sum of the current digits from both input linked lists and the carryover, then generates a new node in the resulting linked list containing the least significant digit of this sum. The carryover for the next iteration is determined as the most significant digit of the sum calculated.
The process continues to loop until both initial linked lists and any remaining carryover values are fully processed. At this stage, the resulting linked list is considered finalized, and the function sends back a reference to its starting node. Within the primary function, two input linked lists are generated, and the addTwoNumbers function is invoked to calculate their total. Subsequently, it loops over the resulting linked list and displays the data stored in each node. In essence, this approach offers a direct and effective resolution for the task of summing two numbers depicted as linked lists in C++. It leverages the prearranged reverse order of input linked lists to streamline the addition process's complexity. Additionally, it employs a placeholder node as the initial point of the resulting linked list to simplify the management of exceptional scenarios.
We begin by generating a placeholder node as the starting point of the fresh linked list. Additionally, we establish a reference called curr that points to the current node being appended to the new linked list. We set carry to 0 initially, to store any remainder from the prior sum calculation. The process involves iterating through both linked lists and the carry value, summing up the matching elements along with any carryover from the previous addition.
If one of the linked lists is shorter than the other, we handle the absent nodes by considering them as having a value of 0. Subsequently, we generate a fresh node by calculating the sum modulo 10 (as the highest sum of two digits is 9 + 9 = 18) and assign the carryover as the sum divided by 10. The pointer "curr" is then updated to point to this newly formed node. Ultimately, we provide the subsequent node following the placeholder node as the output.
