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 <stdlib.h>
2
3struct ListNode {
4 int val;
5 struct ListNode *next;
6};
7
8struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
9 struct ListNode dummy;
10 struct ListNode* current = &dummy;
11 int carry = 0;
12
13 while (l1 != NULL || l2 != NULL) {
14 int x = (l1 != NULL) ? l1->val : 0;
15 int y = (l2 != NULL) ? l2->val : 0;
16 int sum = carry + x + y;
17 carry = sum / 10;
18 current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
19 current = current->next;
20 current->val = sum % 10;
21 current->next = NULL;
22
23 if (l1 != NULL) l1 = l1->next;
24 if (l2 != NULL) l2 = l2->next;
25 }
26
27 if (carry > 0) {
28 current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
29 current = current->next;
30 current->val = carry;
31 current->next = NULL;
32 }
33
34 return dummy.next;
35}This C implementation employs a dummy head node to start building the resultant list. A 'carry' variable is used to keep track of any overflow beyond a single digit, which is added to the next higher digit. The values are summed, and their result is split into carry and remainder, which becomes the node value. The iteration continues until both input lists are exhausted. The remaining carry is checked to append another node if needed.
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.
1public
Java implements the recursive approach where the method addTwoNumbersRecursive handles passing the current nodes of the lists and the carry. It constructs a new ListNode and recurses forward until the lists and carry are exhausted.