Sponsored
Sponsored
This approach involves iterating through both linked lists, node by node, adding corresponding values along with any carry from the previous addition. The result at each step is appended to a new linked list. If one list is longer than the other, the iteration continues on the longer list alone. A final check is done to handle any remaining carry.
Time Complexity: O(max(m, n)) where m and n are the lengths of the input lists. This is because we iterate through each node exactly once.
Space Complexity: O(max(m, n)) to store the resulting list.
1#include <iostream>
2using namespace std;
3
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode(int x) : val(x), next(NULL) {}
8};
9
10class Solution {
11public:
12 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
13 ListNode dummy(0);
14 ListNode* current = &dummy;
15 int carry = 0;
16 while (l1 != nullptr || l2 != nullptr) {
17 int x = (l1 != nullptr) ? l1->val : 0;
18 int y = (l2 != nullptr) ? l2->val : 0;
19 int sum = carry + x + y;
20 carry = sum / 10;
21 current->next = new ListNode(sum % 10);
22 current = current->next;
23 if (l1 != nullptr) l1 = l1->next;
24 if (l2 != nullptr) l2 = l2->next;
25 }
26 if (carry > 0) {
27 current->next = new ListNode(carry);
28 }
29 return dummy.next;
30 }
31};C++ solution follows the same logic as C. The Solution class exposes an addTwoNumbers method which constructs the result list from the dummy node. Continually calculates sum of nodes and carry, creates new nodes for result list, and moves iterators along the lists.
The recursive approach solves the problem by recursing down the linked lists, accumulating values with carry and constructing the result linked list from the returned values from child calls. Each recursive call processes one pair of nodes from the lists, similar to how you would process each position in a sum independently in the iterative version.
Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n)) because of the recursion stack.
1
In this C solution, we define a helper function addTwoNumbersRecursive that takes the two input lists and a carry. The function recursively creates new nodes based on the summed values ensuring that carry is also considered. The base case returns NULL when ends of both lists and no carry remain.