2. Add Two Numbers — LeetCode(Python)
I got you!
Problem:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]Constraints:
- The number of nodes in each linked list is in the range
[1, 100]. 0 <= Node.val <= 9- It is guaranteed that the list represents a number that does not have leading zeros.
Solution:
r = 1
num1 = 0
while l1:
num1 += l1.val * r
r *= 10
l1 = l1.next
r = 1
num2 = 0
while l2:
num2 += l2.val * r
r *= 10
l2 = l2.next
dummy = node = ListNode()
s = num1 + num2if not s:
return ListNode(0)
while s > 0:
r = s % 10
node.next = ListNode(r)
node = node.next
s = s // 10
return dummy.next
Explanation —
This is a very trivial problem.
First we traverse the two lists separately and store the two numbers that they represent.
Since the digits are arranged in reverse order, our work is even lower because we do not manually have to reverse the linked list now.
After storing the numbers, we calculate the sum.
This sum’s digits are accessed from behind using (% 10) which gives us the last digit and (// 10) which removes the last digit.
Each new digit is assigned a node and is connected to the next node.
Finally, the head of the new linked list is returned.
Time and Space Complexity —
Since we are traversing the two lists only once, we can say that our algorithm runs in linear time.
Also, we require a constant amount of extra space if we don’t consider the linked list we are supposed to return.
Thus, if n is the length of the linked list,
Time Complexity: O(n)
Space Complexity: O(1)
