【leedcode】0002. 链数之和
给定两个 非空 的链表用来表示两个非负的整数(即标题中据说的链数定义)。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
class Node(object): def __init__(self, x=None, Next=None): self.val = x self.next = Next def __repr__(self): return f'{self.val}->{self.next}' class List(object): def __init__(self, node=None): self.head = node def __repr__(self): return f'[{self.head}]' def build(self, num): head = None for i in str(num): head = Node(int(i), head) self.head = head return self @property def length(self): ret,ptr = 0,self.head while ptr: ptr = ptr.next ret += 1 return ret @property def value(self): ret,base,ptr = 0,1,self.head while ptr: ret += ptr.val * base ptr = ptr.next base *= 10 return ret def add(self, other): ret = List() if self.length>other.length: ret.build(self.value) ptr1,ptr2 = ret.head,other.head else: ret.build(other.value) ptr1,ptr2 = ret.head,self.head carry = 0 while ptr1: try: tmp = ptr2.val except: tmp = 0 carry,ptr1.val = divmod(ptr1.val+tmp+carry,10) ptr1 = ptr1.next try: ptr2 = ptr2.next except: pass if carry: ptr = ret.head while ptr: if not ptr.next: ptr.next = Node(1) break ptr = ptr.next return ret if __name__ == '__main__': L1,L2 = List(),List() n1,n2 = 342,465 L1.build(n1) L2.build(n2) L3 = L1.add(L2) L4 = L2.add(L1) print(L1,L2,L3,L4,sep='\n') print(L1.value,L2.value,L3.value,L4.value,sep='\n') n1,n2 = 3,999 L1.build(n1) L2.build(n2) L3 = L1.add(L2) L4 = L2.add(L1) print(L1,L2,L3,L4,sep='\n') print(L1.value,L2.value,L3.value,L4.value,sep='\n')
代码这样写的好处是两个加数都保持原来的值,网上好多例子两数加完之后self本身也等于两数之和了。另外,加上方法和属性_repr__(),build(),.length,.value是为了方便检查和创建单链表。
还有在逐位相加时,进位和该位上去掉进位的和用函数divmod来表达也非常简捷有效。
代码运行结果如下:
[2->4->3->None] [5->6->4->None] [7->0->8->None] [7->0->8->None] 342 465 807 807 [3->None] [9->9->9->None] [2->0->0->1->None] [2->0->0->1->None] 3 999 1002 1002