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.
1class ListNode {
2 constructor(val = 0, next = null) {
3 this.val = val;
4 this.next = next;
5 }
6}
7
8function reverseList(head) {
9 let prev = null;
10 while (head !== null) {
11 let nextTemp = head.next;
12 head.next = prev;
13 prev = head;
14 head = nextTemp;
15 }
16 return prev;
17}
18
19function addTwoNumbers(l1, l2) {
20 l1 = reverseList(l1);
21 l2 = reverseList(l2);
22 let dummy = new ListNode(0);
23 let current = dummy;
24 let carry = 0;
25
26 while (l1 !== null || l2 !== null || carry !== 0) {
27 let sum = carry;
28 if (l1 !== null) {
29 sum += l1.val;
30 l1 = l1.next;
31 }
32 if (l2 !== null) {
33 sum += l2.val;
34 l2 = l2.next;
35 }
36 carry = Math.floor(sum / 10);
37 current.next = new ListNode(sum % 10);
38 current = current.next;
39 }
40 return reverseList(dummy.next);
41}For JavaScript, we reverse linked lists initially, then iterate both accounting for possible carries whilst forming the resultant list, which is reversed to ensure order accuracy.
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
In Python, stacks are used for easy reverse-traversal of list digits, managing carry, and gradually forming the output linked list by prepending nodes from the sum operation.