-
Notifications
You must be signed in to change notification settings - Fork 42
/
add-reversed-linked-list.py
91 lines (70 loc) · 2.05 KB
/
add-reversed-linked-list.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
80
81
82
83
84
85
86
87
88
89
90
91
'''Given two reversed linked lists, each representing one integer, add those two linked lists as if they were actual
correct ordered integers and return the result as a reversed linked list.
For example, L1: 0 -> 0 - > 1, L2: 0 -> 0 -> 2, ANS: 0 -> 0 -> 3.'''
class Node():
def __init__(self, x):
self.val = x
self.next = None
class LinkedList():
def __init__(self):
self.head = None
def append(self, x):
newNode = Node(x)
if self.head is None:
self.head = newNode
else:
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = newNode
cur = cur.next
def __iter__(self):
cur = self.head
while cur:
yield cur.val
cur = cur.next
def __str__(self):
res = ""
if self.head is None:
return res
cur = self.head
while cur.next is not None:
res += str(cur.val) + " -> "
cur = cur.next
res += str(cur.val)
return res
def addLists(num1, num2):
res = LinkedList()
carry = 0
while num1.head or num2.head:
if num1.head and num2.head:
tmp = num1.head.val + num2.head.val + carry
if tmp > 9:
carry = tmp // 10
tmp %= 10
else:
carry = 0
res.append(tmp)
num1.head = num1.head.next
num2.head = num2.head.next
elif num1.head:
tmp = num1.head.val + carry
if tmp > 9:
carry = tmp // 10
tmp %= 10
else:
carry = 0
res.append(tmp)
num1.head = num1.head.next
elif num2.head:
tmp = num1.head.val + carry
if tmp > 9:
carry = tmp // 10
tmp %= 10
else:
carry = 0
res.append(tmp)
num2.head = num2.head.next
if carry:
res.append(carry)
return res