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 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def reverseList(self, head):
8 prev = None
9 current = head
10 while current:
11 next_temp = current.next
12 current.next = prev
13 prev = current
14 current = next_temp
15 return prev
16
17 def addTwoNumbers(self, l1, l2):
18 l1 = self.reverseList(l1)
19 l2 = self.reverseList(l2)
20 carry = 0
21 dummy = ListNode(0)
22 current = dummy
23
24 while l1 or l2 or carry != 0:
25 total = carry
26 if l1:
27 total += l1.val
28 l1 = l1.next
29 if l2:
30 total += l2.val
31 l2 = l2.next
32 carry = total // 10
33 current.next = ListNode(total % 10)
34 current = current.next
35
36 return self.reverseList(dummy.next)In Python, after reversing the input lists, this code calculates the sum of corresponding nodes, accounts for any carry, and prepends nodes to build the result list, which is also reversed at completion.
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
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
Stack<int> stack1 = new Stack<int>();
Stack<int> stack2 = new Stack<int>();
while (l1 != null) {
stack1.Push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.Push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode result = null;
while (stack1.Count > 0 || stack2.Count > 0 || carry > 0) {
int sum = carry;
if (stack1.Count > 0) sum += stack1.Pop();
if (stack2.Count > 0) sum += stack2.Pop();
carry = sum / 10;
ListNode newNode = new ListNode(sum % 10);
newNode.next = result;
result = newNode;
}
return result;
}
}This C# solution employs System.Collections.Generic.Stack to manage reverse traversal during addition, prepending resulting nodes to form the required output list patiently.