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 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
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}This Java solution follows a similar pattern: reversing the input lists, adding node values, and managing carry. A dummy node assists in recursively building the final list which is subsequently reversed to present the answer.
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.