前言
本文是为了记录自己刷题的代码，以及之后优化所记的博客。
具体思路
最开始测试用的代码如下：
def addTwoNumbers(l1, l2):
sp=list()
flag=len(l1)+1
for i in range(len(l1)):
s_tmp=l1[i]+l2[i]
if s_tmp>=10:
s_tmp=s_tmp-10
try:
l1[i+1]=l1[i+1]+1
except:
flag=1
sp.append(s_tmp)
try:
a=l1[flag]
sp.append(1)
except:
pass
## print(sp)
return sp
l1 = [2,4,3]
l2 = [5,6,4]
addTwoNumbers(l1,l2)
思路上比较简单，逢十进一，最后一位的时候直接append(1)来实现最高位的加一处理，为了让最高位能够输出1，所以特意加了个flag，来做一个异常处理，在l1[flag]不走except位置的时候说明到了最高位，这时候加一即可。
之后为了将列表格式转为链表格式，所以看了看链表的基本操作：
# 声明链表类
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 链表初始化
ListNode(0,head)
# 到下一个节点
p=p.next
之后利用类似的原理，做出了两个链表长度相同时候的解答：
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
flag=0
head=l1
while(l1.next and l2.next):
s_tmp=l1.val+l2.val
if s_tmp>=10:
s_tmp=s_tmp-10
l1.next.val=l1.next.val+1
l1.val=s_tmp
l1=l1.next
l2=l2.next
# now is coming to the last one
final=ListNode(0,None)
if l1.next and l2.next:
l1.val=l1.val+l2.val
if l1.val>=10:
final.val=1
l1.next=final
print(head)
return head
之后写了个创建新节点的类内函数，增加了一个判断从句，但是没考虑到连续进位的情况：
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
head=ListNode(0,None)
next_nodes=head
while l1.next and l2.next:
sums=l1.val+l2.val
if sums>=10:
l1.next.val=l1.next.val+1
sums=sums-10
next_nodes.val=sums
next_nodes=self.addnode(next_nodes)
print(head)
l1=l1.next
l2=l2.next
if l1.next and not l2.next:
next_nodes.val=l1.val+l2.val
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
l1.next.val=l1.next.val+1
next_nodes.next=l1.next
elif l2.next and not l1.next:
next_nodes.val=l1.val+l2.val
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
l2.next.val=l2.next.val+1
next_nodes.next=l2.next
else:
next_nodes.val=l1.val+l2.val
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
next_nodes=addnode
next_nodes.val=1
print(head)
return head
def addnode(self,cur):
nxt=ListNode(0,None)
cur.next=nxt
return nxt
之后从第一个节点开始扫描，检测到一个大于十的节点就随之给它进位，题目通过，但是排名有点一言难尽：
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
head=ListNode(0,None)
next_nodes=head
while l1.next and l2.next:
sums=l1.val+l2.val
if sums>=10:
l1.next.val=l1.next.val+1
sums=sums-10
next_nodes.val=sums
next_nodes=self.addnode(next_nodes)
print(head)
l1=l1.next
l2=l2.next
if l1.next and not l2.next:
next_nodes.val=l1.val+l2.val
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
l1.next.val=l1.next.val+1
next_nodes.next=l1.next
elif l2.next and not l1.next:
next_nodes.val=l1.val+l2.val
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
l2.next.val=l2.next.val+1
next_nodes.next=l2.next
else:
next_nodes.val=l1.val+l2.val
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
next_nodes=self.addnode(next_nodes)
next_nodes.val=1
next_nodes=head
while next_nodes:
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
try:
next_nodes.next.val=next_nodes.next.val+1
except:
next_nodes=self.addnode(next_nodes)
next_nodes.val=1
next_nodes=next_nodes.next
print(head)
return head
def addnode(self,cur):
nxt=ListNode(0,None)
cur.next=nxt
return nxt
不管是时间上还是内存上排名都比较靠后，可以进步的空间很大：
为了加一部分优化，从一部分开始就往后遍历，新添加了类内函数，修改后代码如下：
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
head=ListNode(0,None)
next_nodes=head
while l1.next and l2.next:
sums=l1.val+l2.val
if sums>=10:
l1.next.val=l1.next.val+1
sums=sums-10
next_nodes.val=sums
next_nodes=self.addnode(next_nodes)
print(head)
l1=l1.next
l2=l2.next
if l1.next and not l2.next:
next_nodes.val=l1.val+l2.val
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
l1.next.val=l1.next.val+1
next_nodes.next=l1.next
self.con_dec(next_nodes)
elif l2.next and not l1.next:
next_nodes.val=l1.val+l2.val
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
l2.next.val=l2.next.val+1
next_nodes.next=l2.next
self.con_dec(next_nodes)
else:
next_nodes.val=l1.val+l2.val
if next_nodes.val>=10:
next_nodes.val=next_nodes.val-10
next_nodes=self.addnode(next_nodes)
next_nodes.val=1
next_nodes=head
print(head)
return head
def addnode(self,cur):
nxt=ListNode(0,None)
cur.next=nxt
return nxt
def con_dec(self,cur):
while cur:
if cur.val>=10:
cur.val=cur.val-10
try:
cur.next.val=cur.next.val+1
except:
cur=self.addnode(cur)
cur.val=1
cur=cur.next
最后结果如下：
优化之后区别不是很大，效果并不显著…
总结：
虽然比较麻烦，而且结果还很差，但是还是记录一下这次的代码，之后再进行相应的优化。