说来惭愧，距离上一次写力扣已经过去一年的时间，在这大四的一年里，从本科前三年的一无所知到现在初入茅庐，有所理解，虽然不堪出口，但进步确实是明显的，然对力扣其实算是荒废了，前面说起要学Java与Cpp，回想也只对Java有所了解，Cpp仍处于门外汉阶段。
不过总归在进步就好，此次回归也要不定期开始刷起来了，重在积累。前面刷的题要好好反思仔细思考记录，后面应该会快一点。
废话少说，这次就接着从第二题开始。
题：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
解题思路：思路想来挺简单的，就是直接将各对应位相加，注意进位就好。不过就是题中所给的是链表，我一时不知道什么是链表（尴尬，不知道Java学了个啥，但确实没掌握这一块）。所幸有度娘，百度之后才发现题中其实给了注释：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next
理解了一下大概是有指针的语言比较能常用的一种结构体，链表的当前节点储存了当前值，和下一个节点的指针。
Python代码：自己上来写的时候直接理解成列表了，所以利用列表求解，并额外写了列表与链表转化的函数，效率当然不大行，最终beat了30左右的人：
class Solution:
def addTwoNumbers(self, l1, l2):
flag = 0 # 设置进位标志位
list1 = self.getlist(l1)
list2 = self.getlist(l2)
len1, len2 = len(list1), len(list2)
calen = min(len1, len2) # 运算长度
resList = []
for i in range(calen):
resList.append(list1[i] + list2[i])
if len1 > len2:
resList.extend(list1[len2:])
if len1 < len2:
resList.extend(list2[len1:])
for i in range(len(resList)):
if flag == 1:
resList[i] += 1
flag = 0
if resList[i] > 9:
resList[i] = resList[i]%10
flag = 1
if (i == len(resList)-1) and (flag == 1): # 最后一位时仍需进位，则往后追加1
resList.append(1)
reslink = self.tolink(resList)
return reslink
def getlist(self, l):
'''
将链表转化为列表
'''
lis = []
while l:
lis.append(l.val) # 当前值赋给列表
l = l.next # 指向下一个链表节点
return lis
def tolink(self, lis):
'''
将列表转化为链表
'''
link = ListNode()
link.next = ListNode(lis[0])
p = link.next
if len(lis) > 0:
for i in lis[1:]:
p.next = ListNode(i)
p = p.next
return link.next
然后是看了大佬的代码，并自己理解了一下，实际上就是直接利用链表节点直接相加进位，值得注意的是其中所谓dummy的东西，其实相当于是创造了一个虚拟的哨兵节点，这样可以将头节点转化为普通的节点，从而简化过程。此外，dummy=p=ListNode()的精髓在于指向了同一个对象的地址，那么在p循环的同时dummy保持了初始位置，因此得以方便地索引。
class Solution(object):
def addTwoNumbers(self, l1, l2):
dummy = p = ListNode(None) # 创建空哨兵节点
flag = 0
while l1 and l2: # 当l1、l2不是空节点的时候循环
if (l1.val+l2.val+flag) > 9: # 在上一位进位后，本位仍需进位时
p.next = ListNode((l1.val+l2.val+flag)%10) # 需在进位后只取个位数字
flag = 1
else:
p.next = ListNode(l1.val+l2.val + flag)
flag = 0 # 进位后重置标志位
p = p.next
l1 = l1.next
l2 = l2.next
l = l1 if l1 else l2
while l:
if (l.val+flag) > 9:
p.next = ListNode((l.val+flag)%10)
flag = 1
else:
p.next = ListNode(l.val+flag)
flag = 0
p = p.next
l = l.next
if flag==1: # 最后一位时仍需进位
p.next = ListNode(1)
return dummy.next
但是发现和自己写的代码运行速度相差不大，但最高beat50左右，最后照搬了大佬的代码：
class Solution:
def addTwoNumbers(self, l1, l2):
dummy = p = ListNode(None) # 创建空哨兵节点
sum = 0 # 设置求和
while l1 or l2 or sum != 0: # l1或l2存在时，或不是两个0相加时才循环
sum += (l1.val if l1 else 0) + (l2.val if l2 else 0) # 存在则相加，不存在加0
p.next = ListNode(sum % 10) # 求和结果求模赋给下一个节点
# 移动到下一个节点
p = p.next
if l1: l1 = l1.next
if l2: l2 = l2.next
sum = sum // 10 # 求和结果取下一位
return dummy.next
过程十分简洁，精妙在只写了一个循环，通过判断是否存在来做加法；同时通过设置求和sum变量求模整除来求得当前位和下一位数，避免了我自己方法设置的进位标志位的麻烦事。
运行速度有浮动，最高40ms快了15ms，但竟然已经beat95%了，看来python用户的确慢啊。。。
最后试用一下这段时间的java代码：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode sumHead = new ListNode(-1);
ListNode sumNode = sumHead;
while (l1 != null || l2 != null) {
// 求和
int x = l1 != null ? l1.val : 0;
int y = l2 != null ? l2.val : 0;
int sum = x + y + carry;
if (sum >= 10) {
carry = 1;
sum = sum - 10;
} else {
carry = 0;
}
sumNode.next = new ListNode(sum);
// 三个指针后移
l1 = l1 != null ? l1.next : null;
l2 = l2 != null ? l2.next : null;
sumNode = sumNode.next;
}
if (carry != 0) {
sumNode.next = new ListNode(carry);
}
return sumHead.next;
}
}
运行速度只要2ms。。。这也太夸张了
后面将直接在力扣上打卡，看心情同步csdn吧。
