Sponsored
Sponsored
This approach involves reversing both linked lists to align the least significant digits and performing the addition operation similarly to how you would add numbers on paper. After the sum is calculated, the result is reversed to restore the original order.
Time Complexity: O(n + m) where n and m are the lengths of the two linked lists. We reverse both lists and then traverse them. Space Complexity: O(1) if we exclude the space required for the output list.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* reverseList(struct ListNode* head) {
10 struct ListNode* prev = NULL;
11 struct ListNode* current = head;
12 while (current != NULL) {
13 struct ListNode* nextTemp = current->next;
14 current->next = prev;
15 prev = current;
16 current = nextTemp;
17 }
18 return prev;
19}
20
21struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
22 l1 = reverseList(l1);
23 l2 = reverseList(l2);
24 struct ListNode dummy;
25 dummy.next = NULL;
26 struct ListNode* current = &dummy;
27 int carry = 0;
28
29 while (l1 != NULL || l2 != NULL || carry) {
30 int sum = carry;
31 if (l1 != NULL) {
32 sum += l1->val;
33 l1 = l1->next;
34 }
35 if (l2 != NULL) {
36 sum += l2->val;
37 l2 = l2->next;
38 }
39 carry = sum / 10;
40 struct ListNode* newNode = malloc(sizeof(struct ListNode));
41 newNode->val = sum % 10;
42 newNode->next = current->next;
43 current->next = newNode;
44 }
45 return reverseList(dummy.next);
46}This solution first reverses both input lists to facilitate adding from the least significant to the most significant digit. We traverse both lists, compute the sum for corresponding nodes, and keep track of any carry forward. The resulting linked list is constructed by prepending nodes. Finally, the resultant list is reversed to represent the correct number.
Another efficient way to solve this problem is using stacks to store digits of both the numbers. This helps to access the least significant digits last, similar to reversing. This allows easier management of carry as we traverse backward effectively without modifying input lists explicitly.
Time Complexity: O(n + m), where n and m are the lengths of linked lists. Space Complexity: O(n + m), for storing numbers in stacks.
1#include <iostream>
#include <stack>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
std::stack<int> s1, s2;
while (l1) {
s1.push(l1->val);
l1 = l1->next;
}
while (l2) {
s2.push(l2->val);
l2 = l2->next;
}
int carry = 0;
ListNode* result = NULL;
while (!s1.empty() || !s2.empty() || carry) {
int sum = carry;
if (!s1.empty()) {
sum += s1.top();
s1.pop();
}
if (!s2.empty()) {
sum += s2.top();
s2.pop();
}
carry = sum / 10;
ListNode* newNode = new ListNode(sum % 10);
newNode->next = result;
result = newNode;
}
return result;
}The C++ solution uses std::stack to record and retrieve the digits. It sums the values and creates nodes for the resultant linked list, appending them in reverse order to form the desired output.