在python数据结构中，常用的有序数组为列表，列表的好处很多，使用也很方便。列表在append元素时时间复杂度为O(1)，但是在insert时复杂度就很高了，因为其需要先找到要插入的索引位置，这个索引之后的所有数据的索引都会+1，导致较耗时；同理删除某个元素也是。
链表
链表是一种数据结构，对于上面提到的在某个位置插入或删除元素的功能能以O(1)的复杂度完成，但缺点是在寻找元素时复杂度为O(n)。这里简要介绍一下链表：实际上链表就是将一系列有顺序的数据以变量的形式储存在内存中，每个变量的一个next属性为按一定顺序的下一个变量，下一个变量的next属性又链接到下下个变量。这里的next是为了方便理解，实际上设置为其它名字也可以，因为这是我们手动给它加上的属性而已嘛。
比如创建一个a→b→c→d→e的链表，a.next就是b这个变量，b.next就是c这个变量，依次类推。当然由于元素都是各种不同的东西（如数字，字符串甚至列表或者字典等），因此每个变量本身还有自己的一个属性才行，这个属性就是变量本身代表的内容。因此这里的a,b,c,d,e可以是分别代表1,2,3,4,5五个元素的，这种属性值才是数据真实存在的意义所在，通过链表储存就让这些数据变得有顺序且利于管理了。因此根据上面提到的，链表是通过创建非常多个变量来储存表内容的，因此当变量将内存占满后，链表就会崩溃哦（当然这种情况应该不太可能会发生，现在电脑的内存一般都较大了）。
下面的一个图简单展示了一个简单的链表。（keys是指a,b,c,d,e，values是指1,2,3,4,5或者"one",“two”,“three”,“four”,"five"这些分别被a,b,c,d,e储存的值（可以是任何内容，这里展示了数字和字符串）。这里的keys和values是为了方便理解，不要和字典搞混啦。）
链表的基础实现
ok，对链表大致有了解了之后，这里实现一下最基础的链表（链表应该有许多类似列表中的功能，如append，remove等，这里就不加入了，大家可以去看看别人的相对更为完整的实现方式）
# 首先，我们能看到上面每一个链表中的变量都有一个属性值，
# 如果要在代码中的每一行分别对这些所有的变量分别赋值，那么也太麻烦了，
# 因此利用python对象的特性，创建一个节点类，在节点类中定义属性值和next属性的来源就可以了。
# 这样每次创建节点时只需要调用一下这个类即可。
# （这里提到的节点就是上面提到的变量，因为链表是有顺序的一一连接的形式，因此称为节点也较为贴切。）
class Node:
def __init__(self, item):
# item表示某个节点所储存的值
self.item = item
self.next = None # next表示其next属性链接的下个变量，默认为None
# 设计好了节点类之后，就可以开始生成链表啦
# 这里先来一个最简单的链表
a = node(1)
b = node(2)
c = node(3)
d = node(4)
a.next = b
b.next = c
c.next = d
# 这里的链表结构就是 a→b→c→d，要查看链表结构可以不断执行next知道next为None（可以做成生成器）
# 显然，这里这样创建链表显得很初级，也比较低效，要使操作链表变简单，最好还是设计一个链表类
class link_list:
def __init__(self):
self.head = None # head表示链表的起始节点
# 下面还有很多方法可以写，这里我就不多写啦
反转链表
迭代的解法
接下来说一下反转链表，反转链表是leetcode中的一道比较经典的题。反转链表也就是要将链表所有元素的顺序反过来，比如这里a→b→c→d就是变为d→c→b→a，其实想想也简单，就是将链表中的每个元素的next变成上一个，但是同时要注意要先记录下一个要变换方向的元素。为什么呢？比如已经将ab间的方向转向后，变为了a←b c→d时，这时候b.next已经不再是c了，因此我们需要多加一个中间变量来让我们记住b，下次让c.next变为b就行了。之后不断重复上述步骤就可以了。我们先来解决一次，这里只写解决的函数。
def rever_list(self):
cur, pre = self.head, None # cur表示当前循环到的节点
while cur:
tmp = cur.next # 先创建一个临时变量
cur.next = pre # 当前节点的next属性变为前一个节点
pre = cur # 这里pre变到cur的位置，cur才能去到下一个节点，
# 这就是上面提到的要记住最开始c的上一个节点是b
cur = tmp # 这里就是要向下一个节点移动，再不停的转换方向
return pre
上面的函数运行后，整个链表的方向被反过来了，因此head（初始节点）位置也变化了，观察函数会发现头节点是被pre这个变量储存着的，因此最后只需要return pre的值，就能从头节点位置不断提取next值并获取到整个链表被反转后的顺序。这里要注意，如果再使用最开始设置的起点（如上面例子中的a），是获取不到完整链表的（而且也是错误结果）。
这里想要提醒的是，根据上面的例子，能够更加体会到链表是一个以变量储存结构的数据结构，因此一个链表是绝对不会被任何一个变量给完全描述的，不像列表一样有一个列表名，也不像字典一样有字典名，链表没有名字，要获取链表的每个值，就需要从链表的头部节点去获取之后的每一个节点，这也是链表中查找某个元素比较慢的原因（要去寻找每一个节点）。
递归解法
理解方式1
除了迭代之外，还有一个递归方式可以解决反转的问题，而且这个递归也是非常巧妙的，也被某些人称作递归的范本。递归我们都知道是不断地去在原函数中去向内深入，直到到达递归的终止条件存在的位置，之后再由终止条件向外回溯，直到回溯到最外层之后就结束。
话不多说先上代码（这里的代码是参考leetcode的代码哦）：
def reverseList_digui1(self):
head = self.head # 先将最开始进递归的位置传入，也就是head（最初的头节点）
def recur(cur, pre):
# 在内部创建递归函数，而在reverseList_digui里创建这个递归函数的原因
# 是因为这是在一个类里面的函数，不能直接传入cur, pre，因此在内部创建递归函数是最理想的
# （实际上就是个闭包函数），这样可以在内部制定变量再不断调用。
if not cur: return pre # 这里是递归终止条件
res = recur(cur.next, cur) # 这里是在不断调用递归函数本身
cur.next = pre # 这里把pre赋值给cur.next，也就是让某个节点处的节点反转了方向
return res
return recur(head, None)
# 闭包函数的基本，在reverseList_digui函数内调用递归函数用以开启递归
看了代码后我是一脸懵，所以先来捋一捋吧，递归最重要是找到结束条件，比如创建一个a=0→b=1→c=2→d=3→e=4→f=5这样的链表，递归函数是不断的传入(cur.next, cur)，也就是当前节点的下一个和当前节点，而且每一轮向里运行就把上一轮的cur.next变为了cur，cur又变为了pre（程序识别的，因为定义时是定义的def recur(cur, pre)）.
而调用递归函数的上一行的if not cur: return pre语句由于没有符合条件，因此是不会运行的，直到传入的cur.next变成了None，同时cur是最后一个节点时，if not cur判断为True，这时候return pre，这里的pre也就是f（值为5），因此上一级的递归获取的res为5，这时候上一级的pre还是之前那一级所传入的pre（为4），cur为5这时候的cur.next = pre就用于将5的下一级节点变为4，再之后return res，可以看到res并没有改变（还是5），但是cur和pre由于之前创建时分别是（1,0）（2,1）（3,2）等，在向外回溯的过程中通过cur.next = pre将这些方向依次都改变了。最终在输入的第一个recur(head, None)也回溯出来后，res的值仍然是5，也就代表着新的头节点，从这个头节点不断的调用next就能将新的反转后的链表列出来。
总结一下，递归函数在这里完成了什么事情呢？
- 使函数不断递归到最后的终止条件，然后将终止条件时的结果（即最后一个节点）取出来，作为最终的结果
- 利用递归包含有回溯的特性，在回溯的每一轮对链表的两个元素的方向进行反转（并且是从后往前的）
这样一理解是不是感觉很神奇，递归就是帮我们找到了最后一个节点，然后再从最后一个节点开始向之前利用递归的特性来对方向进行反转。
理解方式2
除了上面的理解方式，还有另一种理解方式相对较简单，也就是我们使用递归，但是不优先考虑终止条件，而是从最后的结果入手。也就是比如当最后的几个节点全部已经被反转了，只剩最后一个节点了，那么也就是说recur(head.next)已经完成了，只剩下recur(head)这个最外面一层还没有完成了。
那这时候我们要做什么呢？相当于我们在递归函数里要怎么去将这最后一个没有完成反转的节点完成反转。那么可以使用head.next.next = head, head.next =None，也就是要把最后一个节点反转，再把head自身的next属性去掉。
因此代码实现如下：
def reverseList_digui2(self):
head = self.head # 先将最开始进递归的位置传入，也就是head（最初的头节点）
def recur(head):
if not head.next: return head
res = recur(head.next)
head.next.next = head
head.next = None
return res
return recur(head)
这种理解方式可能相对更简单，实现起来也挺简单，可以多理解一下呀。但其实仔细观察也会发现和上面的实现方式几乎是一样的，如果仔细观察下面方式的终止条件，也会发现是递归到没有下一个节点终止。（要注意这里的head可能会误导人，这里的head只是最开始为head，进入递归后head表示的是前面的那个节点）。与上面解法的不同在于这里少了pre这个指针，而仅使用了head.next这一个指针，先把head.next的next变为head（即反转），再把head自身的next属性变为None（即删去最开始存在的方向）。其实这里的head.next属性不变为None对于开始位于链表后面的元素来说是没有影响的（因为后面加上的每个节点新的next会将之前存在的next属性顶替掉），但是对于最开始的0,1节点的问题就会互相产生环（1.next = 0, 0.next = 1）。对于上面的解法不会产生这种现象则是因为开始传入的为（head，None）会把初始节点的next转为None。
python并行赋值
上面的反转链表的后面四行，其实是可以写成一行的，这就是Python里的并行赋值（也就是在一行中完成对多个内容的赋值）。
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
# 可以表示为：
cur.next, pre, cur = pre, cur, cur.next
上面的并行赋值是从左边运行到右边的，也就是先是cur.next变为了pre，pre再变为cur，cur变为cur.next，但是要注意这里最后的cur.next还是最开始的cur.next，因此如果使用cur.next = pre；pre = cur； cur = cur.next这样三句是会报错的，也就是cur最后要改变成最初始的cur.next，而不是变为在cur.next变为pre之后的cur.next。
从这个例子中理解一下，也就是说在同一行中写的语句虽说是从左到右执行，但是使用到的变量值都是这一行之前所存在的变量值，在行内即使有改变值也并不会影响之后所使用到的变量值。
这里再举个例子：
a,b,c = 1,2,3
a,b,c = a+b, a-b, b+c
print(a,b,c)
# 这里的输出为3 -1 5
# 分别对应着最开始的a，b，c三个值的a+b，a-b，b+c的结果
叮
参考：https://leetcode-cn.com/problems/UHnkqh/solution/jian-zhi-offer-ii-024-fan-zhuan-lian-bia-m8go/
参考：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484467&idx=1&sn=beb3ae89993b812eeaa6bbdeda63c494&scene=21#wechat_redirect