-
Notifications
You must be signed in to change notification settings - Fork 0
/
004 Add Two Numbers.py
executable file
·79 lines (64 loc) · 2.01 KB
/
004 Add Two Numbers.py
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
"""
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each
of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
"""
__author__ = 'Danyang'
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def __repr__(self):
# for debugging
return repr(self.val)
class Solution:
def addTwoNumbers(self, l1, l2):
"""
Algorithm: Two pointers & math
Two pointers for l1 and l2 respectively
Math - carry for addition, in the form of new node
:param l1: linked list head node
:param l2: linked list head node
:return: ListNode
"""
result_head = ListNode(0)
cur1 = l1
cur2 = l2
cur = result_head
while cur1 or cur2:
cur.val = cur.val+self.addNode(cur1, cur2)
if cur.val < 10:
if cur1 and cur1.next or cur2 and cur2.next: # next node
cur.next = ListNode(0)
else:
cur.val -= 10
cur.next = ListNode(1)
if cur1:
cur1 = cur1.next
if cur2:
cur2 = cur2.next
cur = cur.next
return result_head
def addNode(self, node1, node2):
"""
Handles None situation
:param node1: ListNode
:param node2: ListNode
:return: integer, summation
"""
if not node1 and not node2:
raise Exception("two nodes are None")
if not node1:
return node2.val
if not node2:
return node1.val
return node1.val+node2.val
if __name__ == "__main__":
l1s = [ListNode(1)]
l2s = [ListNode(9), ListNode(9)]
for i in range(len(l1s)-1):
l1s[i].next = l1s[i+1]
for i in range(len(l2s)-1):
l2s[i].next = l2s[i+1]
Solution().addTwoNumbers(l1s[0], l2s[0])