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 <stack>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
while (head) {
ListNode* nextTemp = head->next;
head->next = prev;
prev = head;
head = nextTemp;
}
return prev;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
ListNode* dummy = new ListNode(0);
ListNode* current = 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;
current->next = new ListNode(sum % 10);
current = current->next;
}
return reverseList(dummy->next);
}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.
1using System.Collections.Generic;
2
3public class ListNode {
4 public int val;
5 public ListNode next;
6 public ListNode(int val = 0, ListNode next = null) {
7 this.val = val;
8 this.next = next;
9 }
10}
11
12public class Solution {
13 public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
14 Stack<int> stack1 = new Stack<int>();
15 Stack<int> stack2 = new Stack<int>();
16
17 while (l1 != null) {
18 stack1.Push(l1.val);
19 l1 = l1.next;
20 }
21 while (l2 != null) {
22 stack2.Push(l2.val);
23 l2 = l2.next;
24 }
25
26 int carry = 0;
27 ListNode result = null;
28 while (stack1.Count > 0 || stack2.Count > 0 || carry > 0) {
29 int sum = carry;
30 if (stack1.Count > 0) sum += stack1.Pop();
31 if (stack2.Count > 0) sum += stack2.Pop();
32 carry = sum / 10;
33 ListNode newNode = new ListNode(sum % 10);
34 newNode.next = result;
35 result = newNode;
36 }
37 return result;
38 }
39}This C# solution employs System.Collections.Generic.Stack to manage reverse traversal during addition, prepending resulting nodes to form the required output list patiently.