-
Notifications
You must be signed in to change notification settings - Fork 0
/
0002. Add Two Numbers
46 lines (40 loc) · 1.71 KB
/
0002. Add Two Numbers
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
39
40
41
42
43
44
45
46
"""
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]
没把数存到list或者多位数,否则需要颠倒再颠倒。而是直接把node数值提出来变成v1,v2
"""
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution: # O(max(m,n)) O(max(m,n))
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# Without dummyhead, need extra conditional statements to initialize the head's value
dummyHead = ListNode(0) # Initialize dummyhead of the result
curr = dummyHead
carry = 0
# Loop through lists l1 and l2 until reach both ends and crarry is 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
col_sum = v1 + v2 + carry
carry = col_sum // 10 # ten digit
val = col_sum % 10 # one digit
curr.next = ListNode(val) # New node with calculated val
curr = curr.next # update curr
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummyHead.next