单链表(线性表的链式存储)
定义：非连续、非顺序的存储结构
数据域+指针域
数据域：存储相应的数据
指针域：存储下一个节点的地址
一些特性：
- 适用于数据数量不能预知的情况
- 逻辑相邻的两元素的存储空间可以不连续
- 链表一般有数据元素和指针域两部分组成
- 存储空间需要动态分配
分类:
- 单向链表
- 双向链表
- 循环链表
一些类型:
- 链表的搜索:查找链表中第一个key= k的元素,返回该元素的指针
LIST-SEARCH(L,K)
x = L.head
while x!=None and x.key !=k
x = x.next
return x
- 链表的插入:给定一个已设置key的元素x,将其接入链表的前端
LIST-INSERT(L,X)
x.next = L.head
if L.head !=None
L.head.prev = x
L.head = x
x.prev = None
- 链表删除:将一个元素从链表中删除
LIST-DELETE(L,X)
if x.prev !=None
x.pre.next = x.next
else L.hea = x.next
if x.next !=None
x.next.prev = x.prev
关于头节点与头指针
- 第一个数据节点的位置被存放在头结点的指针域中，链表的第一个位置上的操作和表的其他位置上操作相同，不用特殊处理
- 无论链表是否为空，头指针都指向头节点的非空指针（空表中头结点的指针域为空），空表和非空表的处理得到统一。
关于链表的解题方法：
先画图（在纸上把过程先画出来），再分析，最后写代码
一般创建单链表，先设置一个虚拟头结点，这样每一个结点都有一个前驱结点，完美解决需要加各种判空逻辑的烦恼。
单向链表的实现
这种纯构造的，只能是对概念十分清楚之后才会做的，而且自己要能够十分熟练的构造出来。
以下的一些图片可以帮助自己去辅助理解相应的一些构造过程
# 总体思路：需要定义两个类，一个是结点类，一个是链表类
# 先定义一个结点类
class ListNode(object):
# 定义结点类的方法
def __init__(self,data):
# self.item 存放自定义的数据
# sele.next 存放下一个结点对象的地址，一开始指向为None
self.data=data
self.next=None
# 定义单向链表类
class SingleLinkList(object):
# 定义链表类的方法,并初始化方法
def __init__(self,node=None):
# 一个私有的head属性，指向None
self.__head=None
# 以下为对象的方法
# 判断链表是否为空
def isempty(self):
# 判断链表是否指向None,如果是None就是空链表
# if self.__head==None:
# return True
# else:
# return False
# 直接返回表达式的结果，把判断的结果当作函数的返回值
return self.__head==None
# 计算链表的长度
def length(self):
count=0
# 定义一个cur指针，让它一开始指向头结点
cur=self.__head
# 让头结点进行移动，直到指向None
while cur !=None:
count+=1
# 把游标往后移动一个位置
cur=cur.next
# 最后返回的就是链表的长度
return count
# 遍历链表的方法
def travel(self):
cur = self.__head
while cur!=None:
# 打印当前的结点
print(cur.item,end=' ')
# 让指向继续向后移动
cur=cur.next
print('')
# 在链表头部添加结点（头插法）
# 这里注意思考的过程，还要注意一个顺序的问题，为了保证原有链表的所有节点不丢掉
# 先操作新节点的next域，让它指向原有的首节点
# 想想特殊的情况，也可以用这三行来表示，不需要进行特殊的判断
def add(self,item):
# 将传入的值构造成结点（把item数据封装成链表所使用的）
node=ListNode(item)
# 1. 将新的节点的链接域next指向头节点
node.next=self.__head
# 2.将链表的头节点指向新节点
self.__head=node
# 在链表的尾部添加节点的方法（尾插法）
def append(self,item):
node=ListNode(item)
# 判断链表是否为空
if self.isempty():
# 直接让self.__head指向node
self.__head=node
# 链表不为空
else:
cur=self.__head
# 这个时候的循环判断条件发生变化
while cur.next!=None:
cur=cur.next
# 循环结束的时候cur.next指向为None
# 修改最后一个节点的指向，将cur.next指向node
cur.next=node
# 在任意的指定位置插入节点的方法
# 同样的思考相应的过程
# 1. 先调整新节点的next域
# 2. 然后再改变原有链表之间的链接关系
def insert(self,pos,item):
# 先找到下标所指的位置在哪
# 考虑pos的特殊情况
# 如果传入的pos是小于等于0的数，默认的将节点插入头部
if pos <0:
self.add(item)
# 如果pos的值大于链表的长度，默认将节点添加到尾部
elif pos>(self.length()-1):
self.append(item)
# 除此之外的情况就包含在内的情况
else:
node=ListNode(item)
# 让pre指针指向头节点的位置
pre=self.__head
# 用来计数
count=0
while count <(pos-1):
# pre指针移动到指定位置的前一个位置（如果移动到指定位置，之后前面的就无法操作了）
# 先去改变node节点的next区域
count+=1
pre=pre.next
# 当循环退出之后，pre指向pos-1的位置
# 修改指向
# 将前一个节点的next指向插入位置节点
node.next=pre.next
# 让pre所指的指向我的节点
pre.next=node
# 删除节点
# 需要两个游标来解决（也可以只用一个游标，但是写法上就不是那么的好理解）
def remove(self,item):
pre=None
cur = self.__head
# 保证之前地每一个节点都被比较过
# 查看特殊地情况：对于空链表，当前地代码满足要求（While不执行）
# 如果要删除地节点恰好是首节点
while cur!=None:
if cur.data==item:
# 先判断次节点是否是头节点
if cur==self.__head:
self.__head=cur.next
else:
# 怎么删除节点
# 整个链表已经完成了一条主线了（这里地理解太关键了）
# 对于只有一个节点地可以这行代码来执行
# 对于要删除最后一个节点也可以用这行代码实现
pre.next=cur.next
# 删除完毕后退出循环
break
else:
# 让两个指针往后移动，始终保证pre在cur的前面
# 这两个游标的移动顺序
pre=cur
cur=cur.next
# 针对返回值问题，有两种
# 1. 返回删除的数据
# 2. 返回要删除的数据的下标（我删除的是链表中的几个元素）
# 查找节点是否存在
# 对于特殊情况也可以表示
def search(self,item):
cur=self.__head
while cur!=None:
# 不断地进行比对
if cur.data==item:
return True
else:
cur=cur.next
return False
# 定义主函数
if __name__=='__main__':
# 初始化一个为空的单向链表
sll=SingleLinkList()
print(sll.isempty())
print(sll.length())
sll.append(10)
sll.append(20)
sll.append(30)
sll.append(40)
sll.append(50)
sll.add(5)
sll.insert(2,35)
print(sll.isempty())
print(sll.length())
sll.travel()
双向链表的实现
同样要把实现方式、存储方式以及这个数据结构所支持的操作函数
每个节点有两个链接，一个指向前一个节点，当此节点为第一个节点时，指向空值；另一个指向一下一个节点，当此节点为最后一个节点时，指向空值。
针对判空，求链表长度以及遍历链表和单链表的方法是一样的，可以采用继承的方式来解决（这里的理解十分的重要，将单链表的类进行封装就可以不用重复再写了，面对对象的思想）
头插法：加入一行代码
尾插法：加入一行代码
在指定位置插入：由于已经有了前驱节点，就只需要一个游标了
# 定义节点类
class ListNode(object):
def __init__(self,data):
self.data=data
self.next=None
self.prev=None
# 定义双向链表类
class DoubleLinkList(object):
def __inint__(self):
self.__head=None
# 判断链表是否为空
def isempty(self):
return self.__head==None
# 计算链表的长度
# 在求长度的过程中就把它当成单链表进行求解就行
def length(self):
count=0
# 定义一个cur指针，让它一开始指向头结点
cur=self.__head
# 让头结点进行移动，直到指向None
while cur !=None:
count+=1
# 把游标往后移动一个位置
cur=cur.next
# 最后返回的就是链表的长度
return count
# 遍历链表的方法
# 和单链表同样
def travel(self):
cur = self.__head
while cur!=None:
# 打印当前的结点
print(cur.item,end=' ')
# 让指向继续向后移动
cur=cur.next
print('')
# 在链表头部添加结点（头插法）
def add(self,item):
# 将传入的值构造成结点（把item数据封装成链表所使用的）
node=ListNode(item)
# 1. 将新的节点的链接域next指向头节点
node.next=self.__head
# 2.将链表的头节点指向新节点
self.__head=node
# 3.原有节点的p区需要改变指向(通过画图来理解,这里需要重点理解)
node.next.prev=node
# 在链表的尾部添加节点的方法（尾插法）
def append(self,item):
node=ListNode(item)
# 判断链表是否为空
if self.isempty():
# 直接让self.__head指向node
self.__head=node
# 链表不为空
else:
cur=self.__head
# 这个时候的循环判断条件发生变化
while cur.next!=None:
cur=cur.next
# 循环结束的时候cur.next指向为None
# 修改最后一个节点的指向，将cur.next指向node
cur.next=node
# 相比单链表，再加入一行代码(把node的前驱指向cur就OK了)
node.prev=cur
# 在任意的指定位置插入节点的方法
def insert(self,pos,item):
# 先找到下标所指的位置在哪
# 考虑pos的特殊情况
# 如果传入的pos是小于等于0的数，默认的将节点插入头部
if pos <0:
self.add(item)
# 如果pos的值大于链表的长度，默认将节点添加到尾部
elif pos>(self.length()-1):
self.append(item)
# 除此之外的情况就包含在内的情况
else:
cur=self.__head
count=0
while count<pos:
count+=1
cur=cur.next
# 循环退出,cur指向pos的位置
node=ListNode(item)
node.next=cur
node.prev=cur.prev
# 然后把原有的两条链接打断,这里的顺序很重要
# 1. 先把前面节点的next指向node
cur.prev.next=node
# 2. cur节点的前驱指向node
cur.prev=node
# 删除节点
# 核心思想要弄懂
# cur.prev.next=cur.next
# cur.next.prev=cur.prev
def remove(self,item):
cur = self.__head
# 只要cur没有到最尾就还是要去找
while cur!=None:
if cur.data==item:
# 先判断次节点是否是头节点
# 在单链表的基础上加上cur.next.prev=None
if cur==self.__head:
self.__head=cur.next
# 对于只有一个节点的情况，还要再加入一个判断（这里不是特别的好想）
# 如果cur.next已经指向空，空的节点没有相应的前驱节点
if cur.next:
cur.next.prev=None
else:
cur.prev.next=cur.next
# 针对如果指向的是最后一个节点的情况，还要再加入一个判断（认真理解）
# 如果cur.next已经指向为None，空的节点没有相应的前驱节点
if cur.next:
cur.next.prev=cur.prev
# 删除完毕后退出循环
break
else:
cur=cur.next
# 查找节点是否存在
# 也是可以当作单链表来对待
def search(self,item):
cur=self.__head
while cur!=None:
# 不断地进行比对
if cur.data==item:
return True
else:
cur=cur.next
return False
# 主函数
if __name__=='__main__'(self):
dll=DoubleLinkList()
print(dll.isempty())
print(dll.length())
dll.append(10)
dll.append(20)
dll.append(30)
dll.append(40)
dll.append(50)
dll.add(5)
dll.insert(2,35)
print(dll.isempty())
print(dll.length())
dll.travel()
单向循环链表的实现
略
以下为一些对应的题目
leetcoad206/92-反转链表和反转链表II（easy/middle）
这道题是一道很经典的题目。很适合理解一些常用的算法以及递归的知识，值得自己反复的去做，反复的去刷，理解其中的一些内涵！！！属于必做和必须深入理解的类型。
反转链表：
leetcoad链接：https://leetcode-cn.com/problems/reverse-linked-list/
视频链接：<>
题目要求：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
常规思路：采用递归的写法
首先要明白递推公式的含义：对于节点1来说：只需要知道它之后的所有节点反转之后的结果就可以了，也即递推公式的含义：把拿到的链表进行反转，然后返回新的头结点
结点1之后的结点，经过递归公式reverseList处理之后的结果如下图：
看了很多的题解之后才发现当初自己根本没有把每一行的代码正真的弄懂
def reverseList(self, head):
# 调用递推公式反转当前结点之后的所有结点
# 返回的结果是反转后的链表的头结点
接下来要做的是反转结点1，将head指向的结点作为其下一个结点的下一个结点head.next.next=head
最后，将head指向的结点下一个结点置为None，就完成了整个链表的反转
寻找递归的终止条件
- head指向的节点为null（空表）
- head指向的节点的下一个节点为null（只有一个节点）
不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点(理解：到最后一个节点的时候，由于当前节点的next节点是空，该节点就是反转成功后的头节点，会直接的返回head)
- cur = self.reverseList(head.next)
- head.next.next = head #去设置当前节点的下一个节点等于xxx 也即：让当前节点的下一个节点的next指针指向当前节点
- head.next = None #让当前节点的next指针指向null
把每一次反转后的结果传递给上一层:return cur（每次返回的cur是最后一个节点，在递归函数内部改变的是当前节点的指向）
核心中的核心：当前链表的次节点往后都已经反转好了，只要反转头两个节点就好了。用下面的这张动图来辅助理解。递归的写法往往是抽象的，确实很难理解。十分锻炼自己的抽象思维能力。
# 递归
class Solution(object):
def reverseList(self, head):
#递归的终止条件：当前为空或者下一个为空（当前为空是为了防止链表不存在的情况）
#正确的说法应该是：当链表只有一个节点或者是空表的情况，啥也不用干，直接返回head
if(head == None or head.next == None):
#此处属于第一次返回，当遍历到最后一个节点的时候触发
return head
#这里的cur就是最后一个节点，也即新链表的头结点
cur = self.reverseList(head.next)
#从这里开始，节点开始反转，节点的下一个节点的下一个节点指向它本身了。
head.next.next = head
#同时把头节点的下一个节点指向空（原先是指向顺序结构的，现在指向反转，防止循环指向）
head.next = None
#把下一个递归过程的结果传递给上一个递归过程
#每层的递归函数都返回cur，就是最后一个节点，理解为返回的是已经反转过的那部分的头指针，而恰好头指针是确定的。
return cur
非递归（双指针迭代）：
这里点当时自己是理解了好久好久，甚至是在图上画了一遍又一遍的演示过程，才慢慢的理解其中的一些过程的，用迭代的写法可以弄懂里面每一步的细致过程。
在遍历列表时，将当前节点的next指针改为指向前一个节点（这一过程就是反转），由于节点没有引用其前一个节点，必须事先存储前一个节点，在更改引用之前，还需要存储后一个节点，最后返回新的头引用。
解题思路如下：将链表所有节点的next指针指向它的前面的节点（如果不考虑递归的细节，这就是一个大的方向）
- 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
- 把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点的指针。
- 改变cur->next节点的指向，将它指向pre(反转了第一个节点，也是很重要的一步过程：每次迭代到cur，都将cur的next指向pre)
- 更新pre和cur指针（pre指针后cur指针分别后移一位），都迭代完了，pre就是最后一个节点
- pre = cur
- cur = tmp
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur = head #定义一个cur指针，指向头节点head
pre = None #定义一个pre指针，初始化为None
while(cur !=None): #当cur为空的时候循环结束，不断的将cur指向pre的过程
temp = cur.next #保存一下 cur的下一个节点，因为接下来要改变cur->next
cur.next = pre #反转
#更新pre、cur指针
pre = cur
cur = temp
return pre
反转链表II:
将链表的部分元素进行反转
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
仍然是辅助一些图片来加深理解：
在这里，head指向结点1，不用关注其后的所有结点如何将m=3与n=5之间的部分是如何反转的，只需要知道反转之后的结果就行了，也即这里的递推的公式的含义为：将拿到的链表反转，然后返回反转后的链表的头结点
class Solution(object):
def reverseBetween(self, head, m, n):
between = self.reverseBetween(head.next,m-1,n-1)
接下来将递推公式返回的结果挂在head之后，即 head.next=between
class Solution(object):
def reverseBetween(self, head, m, n):
between = self.reverseBetween(head.next,m-1,n-1)
head.next=between
return head
递推的部分已经完成了，现在就是需要明确递归的终止条件
原问题： 反转链表1–>2–>3–>4–>5–>None m=3和n=5之间的部分
更小的子问题：反转链表：2–>3–4–5–6–>None m=2和n=4之间的部分
进一步的反转链表：3–4–5–6–>None m=1和n=3之间的部分
通过分析我们知道，当m==1的时候，递归需要停止
class Solution(object):
def reverseBetween(self, head, m, n):
if m==1:
return pass
between = self.reverseBetween(head.next,m-1,n-1)
head.next=between
return head
接下来的重点问题就是如何利用递归的思想反转3–4–5–6–>None m=1和n=3 即如何反转链表的前n个结点
借用东哥的代码的思路，需要的参数有两个：带反转的链表的头结点 以及 反转前几个结点（n值）
因此写出反转前n个结点的函数
def reverseN(head,n):
# 当反转的就是第一个节点，直接返回头节点就行
if n == 1:
return head
# 以 head.next 为起点，需要反转前 n - 1 个节点
last = reverseN(head.next, n-1)
successor = head.next.next
# 以head.next为开头的链表已经完成翻转，那么head.next.next正确指向后继节点
head.next.next = head
head.next = successor
return last
leetcoad链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/
视频链接：https://ke.algomooc.com/detail/v_621d9b82e4b066e9608a2c07/3
参考leetcoad上的一篇题解：
https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/java-shuang-zhi-zhen-tou-cha-fa-by-mu-yi-cheng-zho/
解题思路：（此道题的解题思路要和合并两个有序链表那题一起来看，重要的是思路+代码实现）
- 一开始设置一个虚拟节点，为了让原链表的所有节点都可以按照统一的方式进行翻转
- 让虚拟节点指向原链表的头部
- 设置一个虚拟指针，指向以虚拟节点为链表的头部位置
- 设置一个指针，指向原链表的头部位置
- 从虚拟头节点出发，pre走left -1步找到需要翻转的左区间
- for循环：结束后，pre的右节点就是要翻转的节点，cur指向就是需要翻转的节点
+ pre不断的向右移动，直到找到翻转的左区间为止
+ cur不断的向右移动，找到需要翻转的第一个节点 - 开始翻转这些节点：（最要的三句代码）
- 设置临时变量，保存当前需要翻转节点的后面的节点
+ 让temp和cur两个节点翻转：cur.next = cur.next.next(想让2的下一个节点不是3而是4，就需要需要把cur的下一节点指向temp的下一个节点)
+ temp.next = pre.next（执行代码的目的：让temp的下一个节点是2而不是4
+ pre.next = temp(pre的下一节点是等号右侧的值) - 最后返回虚拟头节点的下一个节点（虚拟头节点不在链表中，用完之后就可以丢弃了）
附上相关的代码：
#本质上采用的是双指针+头插法
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
#此处定义虚拟指针是为了方便处理（但凡是需要考虑左右边界的时候就需要考虑虚拟节点）
#设置一个虚拟节点，指向原链表的头部
dummy = ListNode(-1)
#让虚拟节点指向原链表的头部
dummy.next = head
#初始化指针的位置
#设置一个虚拟指针，指向以虚拟节点为链表的头部位置
pre = dummy
#设置一个指针，指向原链表的头部位置
cur = head
#将指针移动到相应的位置
#从虚拟节点出发，pre走left-1步找到需要翻转的左区间
#for循环：结束后，pre的右节点就是要翻转的节点，cur指向的就是要翻转的节点（需要结合相应的动画来理解）
for _ in range(left -1):
#pre不断的向右移动，直到走到翻转的左区间为止
pre = pre.next
#cur不断的向右移动，找到了需要翻转的第一个节点
cur = cur.next
#开始翻转这些节点（也即用头插法插入节点）
for _ in range (right -left):
#设置临时变量，保存当前需要翻转节点的后面的节点
temp = cur.next
#接后面
cur.next= cur.next.next
#头插
temp.next = pre.next
pre.next = temp
#最后返回虚拟头结点的下一个节点（虚拟头结点不在链表中，用完之后就可以丢弃）
return dummy.next
#时间复杂度：O(N):N是链表节点总数，最多只遍历了链表一次
#空间复杂度：O(1)：只使用到了常数个变量
递归版本：
# 递归的思路太难想了，要写的化还是迭代的思路要清晰一些
class Solution(object):
def reverseBetween(self, head, m, n):
# 借助反转前n个节点的函数
def reverseN(head,n):
# 当反转的就是第一个节点，直接返回头节点就行
if n == 1:
return head
# 以 head.next 为起点，需要反转前 n - 1 个节点
last = reverseN(head.next, n-1)
successor = head.next.next
# 以head.next为开头的链表已经完成翻转，那么head.next.next正确指向后继节点
head.next.next = head
head.next = successor
return last
# 如果m==1,就像相当于
if m == 1:
return reverseN(head,n)
head.next = self.reverseBetween(head.next,m-1,n-1)
return head
leetcoad21/23-合并两/k个有序链表(easy/hard)
合并两个有序链表
leetcoad链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/
视频链接：https://www.algomooc.com/658.html
解题思路如下：
+ 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值（dummy）
+ 设置一个指针，指向虚拟节点(pre = dummy)
+ 通过一个循环，不断的比较L1和L2中当前节点值的大小，直到L1或者L2遍历完毕为止（指出这个循环就是问题的关键）
+ 如果 l1 当前节点的值小于等于了 l2 当前节点的值
+ 让 pre 指向节点的 next 指针指向这个更小值的节l1
+ 让 l1 向后移动
+ else：
+ 让 pre 指向节点的 next 指针指向这个更小值的节l2
+ 让 l2 向后移动
+ 让pre向后移动
+ 跳出循环后，L1或l2中可能有剩余的节点没有被观察过
+ 直接把剩下的节点加入到pre的next指针位置
+ 如果 l1 中还有节点
+ 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
+ 如果 l2 中还有节点
+ 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
+ 最后返回虚拟节点的next指针
自己调试的版本：
#定义节点
class ListNode():
def __init__(self, x):
self.val = x
self.next = None
#将传入的数组转化为链表
def create_linked_list(arr):
head = ListNode(arr[0])
cur = head
for i in range(1, len(arr)):
cur.next = ListNode(arr[i])
cur = cur.next
return head
#传入链表头节点，以数组形式返回
def print_linked_list(head):
cur = head
res = []
while cur:
res.append(cur.val)
cur = cur.next
return res
class Solution():
def mergeTwoLists(self, l1, l2):
pre = ListNode(0)
head = pre
while l1 and l2:
if l1.val >= l2.val:
pre.next = l2
l2 = l2.next
else:
pre.next = l1
l1 = l1.next
pre = pre.next
pre.next = l1 if l1 else l2
return head.next
if __name__ == "__main__":
head1 = create_linked_list([1, 2, 4])
head2 = create_linked_list([1, 3, 4])
solution = Solution()
sorted_lists = solution.mergeTwoLists(head1, head2)
print(print_linked_list(sorted_lists))
#输出：[1, 1, 2, 3, 4, 4]
吴师兄给的思路的方法：
class Solution:
def Merge(self , L1: ListNode, L2: ListNode) -> ListNode:
#设置一个虚拟节点,因为不知道构建的结果中，开头的元素到底是l1还是l2,就是为了在后面比较后加入才直到，所以设置后就可以不用管了
dummy = ListNode(-1)
#设置一个虚拟指针，指向虚拟节点。这个虚拟指针是可以移动的，目的是让指针指向链表的最后一个元素，可以是l1，也可以是l2,是按照从小到大的顺序不断的进行移动的
pre = dummy
#通过一个循环，不断的比较L1和L2中当前节点值的大小，直到L1或者L2遍历完为止
while L1 and L2:
#如果L1对应的节点值更小，就把pre指向节点的next指针指向L1
if L1.val <= L2.val:
pre.next = L1
#然后把L1向前移动（很重要的一步）
L1= L1.next
#如果L2对应的节点值更小，就把pre指向节点的next指针指向L2
else:
pre.next = L2
#然后把L2向前移动
L2 = L2.next
#让pre不断的向后移动
pre = pre.next
#跳出循环后，L1和L2中可能有剩余的节点没有观察到
#直接把剩下的节点加入到pre的next指针位置
if L1 !=None:
pre.next=L1
if L2 !=None:
pre.next = L2
return dummy.next
尝试写一下递归的版本：
合并k个升序链表
leetcoad链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/
这题是在合并两个有序链表的基础上衍生出来的（把递归的知识再融合进去）
代码待填充.......
leetcoad25-每k个一组翻转链表
Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 采用迭代地思路解题
dummy=ListNode(-1)
dummy.next=head
# 设置两个指针，一个pre指针指向虚拟结点，一个end指针，初始时指向虚拟结点，后面表示每次要翻转地链表地尾结点
# pre:-1-->1-->2-->3
# end:-1-->1-->2-->3
pre,end=dummy,dummy
# 通过循环不断地找到翻转链表的尾部
while end.next!=None:
for i in range(k):
if end is None:
break
else:
# end不断地向后移动，移动k次达到每一组翻转链表地尾部
end=end.next
# 如果发现end==None，说明此时翻转地链表地节点数小于k，保存原有的顺序
if end is None:
# 直接跳出循环，执行下面的翻转操作
break
# next表示【待翻转区域】里面的第一个结点
next=end.next
# 翻转区域的最尾部结点先断开
end.next=None
# start表示【翻转区域】里面的第一个结点
start=pre.next
# 此时翻转区域的头结点时start，尾结点时end,执行后续的翻转操作
# start-->--->end 变成 end--->---->start
# 要翻转的链表的头结点的【上一个节点】的 next 指针指向这次翻转的结果
pre.next=self.reverseList(start)
# 【翻转区域】里面的尾结点的next指针指向【待翻转区域】的第一个结点
start.next=next
# pre表示每次翻转的链表的头结点的上一个结点
pre=start
# 将end重置为[待翻转链表区]的头节点的上一个节点
end=start
return dummy.next
def reverseList(self,head:ListNode):
if(head == None or head.next == None):
return head
cur = self.reverseList(head.next)
head.next.next = head
head.next = None
return cur
leetcoad142-环形链表II(middle)
leetcoad链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/
视频链接：https://www.algomooc.com/746.html
涉及到的知识点:快慢指针
有一些理解的东西可能也很重要，自己要内化成为自己的东西