0002. Add Two Numbers
Medium | Linked List + Math | 52 ms (94.00%), 13.6 MB (45.02%)
Source: LeetCode - Add Two Numbers GitHub: Solution / Performance
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.
Constraints:
The number of nodes in each linked list is in the range
[1, 100].0 <= Node.val <= 9It is guaranteed that the list represents a number that does not have leading zeros.
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]For each iteration, we need to check whether either l1 or l2 arrives at the end.
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
cur = ListNode()
ret = cur
carry = 0
# ==================================================
# Linked List + Math =
# ==================================================
# time : O(max(n, m))
# space : O(1)
while l1 or l2:
if l1:
num1 = l1.val
l1 = l1.next
else:
num1 = 0
if l2:
num2 = l2.val
l2 = l2.next
else:
num2 = 0
val = num1 + num2 + carry
carry = val // 10
cur.next = ListNode(val % 10)
cur = cur.next
# check carry to see if need to create extra node
if carry != 0: cur.next = ListNode(carry)
return ret.nextclass Solution {
/**
* @time : O(max(n, m))
* @space : O(1)
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur = new ListNode();
ListNode ret = cur;
int carry = 0;
while(l1 != null || l2 != null) {
int num1, num2;
if(l1 != null) {
num1 = l1.val;
l1 = l1.next;
} else num1 = 0;
if(l2 != null) {
num2 = l2.val;
l2 = l2.next;
} else num2 = 0;
int sum = num1 + num2 + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
}
if(carry != 0) cur.next = new ListNode(carry);
return ret.next;
}
}
Last updated
Was this helpful?