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 <iostream>
2#include <stack>
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode(int x) : val(x), next(NULL) {}
8};
9
10ListNode* reverseList(ListNode* head) {
11 ListNode* prev = NULL;
12 while (head) {
13 ListNode* nextTemp = head->next;
14 head->next = prev;
15 prev = head;
16 head = nextTemp;
17 }
18 return prev;
19}
20
21ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
22 l1 = reverseList(l1);
23 l2 = reverseList(l2);
24 ListNode* dummy = new ListNode(0);
25 ListNode* current = dummy;
26 int carry = 0;
27
28 while (l1 || l2 || carry) {
29 int sum = carry;
30 if (l1) {
31 sum += l1->val;
32 l1 = l1->next;
33 }
34 if (l2) {
35 sum += l2->val;
36 l2 = l2->next;
37 }
38 carry = sum / 10;
39 current->next = new ListNode(sum % 10);
40 current = current->next;
41 }
42 return reverseList(dummy->next);
43}Similar to the C version, this C++ solution reverses both linked lists, adds corresponding digits and forms the result list which is again reversed at the end. A dummy node is used to simplify handling the list operations.
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
JavaScript arrays are utilized as stacks here, enabling reverse order access for efficient arithmetic processing and forming nodes for the output linked list. This avoids needing to modify input lists directly.