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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int value) { val = value; }
5}
6
7public class Solution {
8 private ListNode Reverse(ListNode head) {
9 ListNode prev = null;
10 while (head != null) {
11 ListNode nextTemp = head.next;
12 head.next = prev;
13 prev = head;
14 head = nextTemp;
15 }
16 return prev;
17 }
18
19 public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
20 l1 = Reverse(l1);
21 l2 = Reverse(l2);
22 ListNode dummy = new ListNode(0);
23 ListNode current = dummy;
24 int carry = 0;
25
26 while (l1 != null || l2 != null || carry != 0) {
27 int 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 = sum / 10;
37 current.next = new ListNode(sum % 10);
38 current = current.next;
39 }
40 return Reverse(dummy.next);
41 }
42}In C#, this method mirrors other languages by first reversing both input lists, adding nodes retain their summed values, accounting any carry, forming the entire output which it reverses finally.
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.