[Leecode刷题]2. 两数相加
题目介绍
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
自己的想法
刚看完题就蒙住了。。仔细思考一下感觉：
- 首先应该判断数字开头不为0等异常
- 把链表中的数字拿出来变成数字
- 然后把数字相加
- 把得到的数字再以倒序的方式插入空列表中
尝试实现结果发现实现不出来（菜狗的悲伤…）主要问题是不会对python类的使用，还有对链表的不熟悉。开始的时候把链表当成了列表，结果一堆bug…然后发现链表和列表区别还是很大的。
实在解不出来，还是去看了答案，然后发现官方没给python版本的解答。所以自己搜索了大佬的解答：原文链接https://blog.csdn.net/zhangyu4863/article/details/80669819
# -*- coding: UTF-8 -*-
# Definition for singly-linked list.
# class ListNode: # 定义链表节点类
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution: # solution解决方案
def addTwoNumbers(self, l1, l2): # 定义两数相加函数
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
# 如果有一个链表为空，返回另外一个
if l1 is None:
return l2
if l2 is None:
return l1
# tmp是暂存（temporal）
tmp = ListNode(0) # 引用ListNode类定义了一个链表节点并赋给tmp
# res是重置（reset）
res = tmp # 赋值
# flag 标示
flag = 0 # 初始化
while l1 or l2: # l1或l2不为空就持续执行
tmp_sum = 0 # 链表节点值的和
if l1: # 如果l1不为空，把l1的某个节点值的和赋给tmp_sum
tmp_sum = l1.val # 把l1的某个节点的值赋给tmp_sum
l1 = l1.next
if l2: # 如果l2不为空，把l2中和l1对应的节点的值加到tmp_sum
tmp_sum += l2.val
l2 = l2.next # 指向下一个节点，为下一次的加和做准备
tmp_res = ((tmp_sum + flag) % 10) # 个位数字
flag = ((tmp_sum + flag) // 10) # 进位的数
res.next = ListNode(tmp_res)
res = res.next # res后移
if flag: # 如果flag不为0，就是对应位置相加后有进位
res.next = ListNode(1) # res的下一节点设为1
res = tmp.next # 赋值
del tmp # 删除tmp变量
return res # 返回res链表
问题解答
我发现我真的会把问题想得太复杂…还把链表转换成列表再计算（手动捂脸）。这个代码想了一个晚上，这里想大概记录一下大佬的思想（不知道理解的对不对）：
- 判断链表是否为空（这里思考的比我多一步，如果其中一个为空，则返回另外一个链表，因为任何数加一个空链表都为自己本身）
- 初始化一个节点（listnode）和一个标记（flag，用来判断是否有进位的标志），设置一个指针（res）指向初始化的节点。
- 在l1或者l2不为空的时候进行循环：
- 初始化一个变量（tmp_sum）用来存储对应节点相加的值
- 把l1的值赋值给tmp_sum，然后指针指向l1下一个节点；
- 把l2对应位置的值加到tmp_sum，指针指向l2下一个节点；
- 如果其中一个链表空了，则直接添加另一个列表剩下的值；
- (tmp_sum+flag)%10是取个位数字（如果没有进位则是直接相加，比如3+5=8，则对对应这两个节点的和的个位为8；如果有进位，比如8+5=13，则对应这两个节点的和为3）
- 然后更新flag的值（(tmp_sum + flag) // 10）
- 然后把得到个位的数字添加到链表下一位，并把指针移到下一位；
- flag不为0 时把链表下一位的值设置为1，这样在下次相加时可以添加进位（比如5+8=13，取出各位数字3后，把下一位的值设置为1，这样在下一位计算时可以直接把进位加进去）
-
res = tmp.next # 赋值这一步大概是让指针指向链表的末尾？（这一步不是很理解） - 最后返回得到的链表即为所求。
一些补充
一、链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。（来自百度百科）
本人看法：链表和列表的区别在于链表只能一个节点一个节点挨着处理，而列表可以随意读取其中的值，而且链表不能使用len()函数（手动捂脸。。）
二、python类
附上python官方介绍：https://www.runoob.com/python/python-object.html
在调用类时必须先创建一个类的对象，然后才能通过对象调用其中的函数。这和直接创建函数直接调用还是有很大区别。