Leetcode 2. Add Two Numbers
Explanation for Leetcode 2 - Add Two Numbers, and its solution in Python.
Problem
Example:
1
2
3
4
5
6
7
8
9
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Input: l1 = [0], l2 = [0]
Output: [0]
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Approach
We can solve this problem by iterating through l1 and l2 linked list with carry.
Our new node is going to be the (l1.val + l2.val + carry) % 10, where carry represents the previous nodes’ carry-ons.
We repeat this process until l1 and l2 are empty and if there’s still carry-on left, we include it to the linked-list.
Here is the Python code for the solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
carry = 0
head = ListNode(0)
curr = head
while l1 and l2:
val1 = l1.val
val2 = l2.val
node = ListNode((val1+val2+carry) % 10)
carry = (val1+val2+carry) // 10
curr.next = node
curr = node
l1 = l1.next
l2 = l2.next
while l1:
val1 = l1.val
node = ListNode((val1+carry) % 10)
carry = (val1+carry) // 10
curr.next = node
curr = node
l1 = l1.next
while l2:
val2 = l2.val
node = ListNode((val2+carry) % 10)
carry = (val2+carry) // 10
curr.next = node
curr = node
l2 = l2.next
if carry:
curr.next = ListNode(carry)
return head.next
Time Complexity and Space Complexity
Time Complexity: $O(n)$
Space Complexity: $O(1)$
This post is licensed under CC BY 4.0 by the author.