在总结链表题前，先记录一个误区：
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
tmp = ListNode(0)
res = temp问题是：tmp和res是代表什么？两个相同链表的头结点？指向两个相同链表的头结点？
解答：tmp和res指向的是存储 哑节点0 的位置，此时tmp和res存储的是同一内存地址，可以理解成tmp和res是两个指针。当对res进行操作时，会在res中存储内容（节点）即为这个内存放内容。而res不断移动，tmp还是指向原来的 哑节点的位置。
但是我们之前用python列表时，情况如下
a = [1, 2]
b = a
b += [3]
print(a) #a = [1, 2]
print(b) #b = [1, 2, 3]为什么改变b却不能改变a呢？那是因为列表是可变对象，对于可变对象，地址是不可以共享的，也就是a,b指向的地址是不一样的。
总结：在python中，不可变对象是共享的（如节点对象），创建可变对象永远是分配新地址（如列表）。
常见的链表题错误
在quick移两个指针的时候，要这样写，要不quick为None时，quick.next会报错。多使用哑节点。
while quick and quick.next:
quick = quick.next.next链表题中，能用一个指针用一个指针，能用两个不用三个，而且都要建立哑节点，并对需要的指针进行初始化。
如删除链表重复的节点的题目。
在链表题中，常用的函数有：
def to_kth_node(head, k):#head为第一个结点，k为第k个结点
k -= 1
p = head
while k > 0 and p:
p = p.next
k -= 1
return p接下来进入链表的题目，做题顺序：2、19、21、23、24、25、61、83、82、86、92
【leetcode2两数相加】
题目：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807思路：这道题的关键在于进位问题，即当两个数相加大于10，需要向高位进一位。因此，设置进位变量为flag。
但是这道题要想完全做对的关键在于，l1和l2不一样长，而且要判断while循环完后是否有进位的情况。自己在写完常规思路以后一定要想一下是否满足特殊情况，把特例测试一下。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None:
return l2
if l2 is None:
return l1
# tmp是暂存（temporal）
tmp = ListNode(0) # tmp指向哑节点
# res是重置（reset）
res = tmp # res指向哑节点（此时和tmp指向同一位置）
# flag 进位标志
flag = 0 # 初始化 （只可能是0或1）
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 # 找到头结点，并赋给res
del tmp # 删除tmp变量
return res # 返回res链表（链表返回只需要返回头节点） 复杂度分析：
时间复杂度：O(max(m,n)),其中m表示l1链表的长度，n表示l2链表的长度
空间复杂度：O(max(m,n)),新链表的长度最多为max(m,n)+1
总结：1、请注意，我们使用哑结点来简化代码。如果没有哑结点，则必须编写额外的条件语句来找到表头，而使用哑节点，可以很快找到表头，因为此时res已经在链表尾部了。2、在写代码的过程中，考虑一下特殊情况，如下表
参考：leetcode题解https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/
哑节点除了能快速找到新链表表头以外，还能简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。
【Leetcode19删除列表的倒数第N个节点】
题目：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.思路：本质是删除题，属于链表的基本操作。当时想到的方法是用两次遍历，第一次遍历先知道链表一共有多少个节点，第二次遍历找到需要删除节点的前一节点。该题我写了三个版本的代码，累死个人。
代码1：没有用到哑节点，把删除分成三种情况，头节点，中间节点，尾节点，两次遍历
代码2：用到哑节点，把删除分成两种情况，尾节点和其它节点，两次遍历
代码3：用到哑节点，两个指针，一次遍历:一次遍历的原因是让两个指针之间间隔n个结点，这样让一个指针到尾节点结束，另一个指针即为要删除结点的上一结点。特别注意的是两个指针间隔n个结点，之前一直弄错成n-1了!!!
贴出代码：
代码1：没有用到哑节点，把删除分成三种情况，头节点，中间节点，尾节点，两次遍历
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
p = head
tmp = p
listnode_n = 0
while p:
listnode_n += 1
p = p.next
p = tmp
if n == 1: #删除尾节点的情况
if listnode_n == 1:
return None
else:
for i in range(listnode_n-2):
p = p.next
p.next = None
return tmp
if n == listnode_n: #删除头节点的情况
return tmp.next
else:
diff = listnode_n - n
if diff > 1:
for j in range(diff-1):
p = p.next
m = p.next
p.next = m.next
return tmp代码2：用到哑节点，把删除分成两种情况，尾节点和其它节点，两次遍历
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)#总结：第一次做分为三种情况，删除头节点，删除中间节点，删除尾节点,后来发现尾节点和中间节点情况一样，只需要考虑头节点和中间节点，但是引入哑节点可以解决头节点的问题。从而不用考虑删除头节点的情况，而且方便返回新链表
dummy.next = head
p = head
length = 0
while p:
length += 1
p = p.next
q = dummy
diff = length - n
while diff:
q = q.next
diff -= 1
q.next = q.next.next
return dummy.next代码3：用到哑节点，两个指针，一次遍历
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)#一次遍历的方法（进阶版）；建立哑节点，并且将哑节点指向head
dummy.next = head
p = dummy
q = p
s = n + 1 #假设最后一个节点是null
while s:
p = p.next
s -= 1
while p:
q = q.next
p = p.next
q.next = q.next.next
return dummy.next
#总结：第一次做分为三种情况，删除头节点，删除中间节点，删除尾节点,后来发现尾节点和中间节点情况一样，只需要考虑头节点和中间节点，但是引入哑节点可以解决头节点的问题。从而不用考虑删除头节点的情况，而且方便返回新链表单独写函数to_kth_node(head, k)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if head is None or n <= 0:
return None
dummy = ListNode(0)
dummy.next = head
p = dummy
q = head
q = self.to_kth_node(q, n+1)
while q:
p = p.next
q = q.next
p.next = p.next.next
return dummy.next
def to_kth_node(self, head, k):
k -= 1
post = head
while k > 0 and post:
post = post.next
k -= 1
return post复杂度分析：
时间复杂度分析：O(n)
空间复杂度分析：O(1)
总结：
- 链表题一定要用哑节点（便于返回头节点，便于删除操作不考虑头节点的特殊情况
- 双指针可以做到只需一次遍历。
【leetcode21合并两个有序链表】
题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4思路：要明白链表的性质就是，如果返回节点1，后面一串都会返回。这道题根本上一个节点添加的问题。哑节点必备。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
q = dummy
p1 = l1
p2 = l2
while p1 and p2:
if p1.val <= p2.val:
q.next = p1
p1 = p1.next
else:
q.next = p2
p2 = p2.next
q = q.next
if p1:
q.next = p1
if p2:
q.next = p2
return dummy.next
#这个链表一定要明白，我每次都是得到当前节点，但是后面还有一大串节点，注意新链表q的移动[q = q.next]复杂度分析：
时间复杂度分析：O(n)，n为链表节点数
空间复杂度分析：O(1)
【leetcode23合并K个有序链表】
题目：合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6思路：在之前合并两个排序链表的基础上，需要k-1次两两合并。进阶：进行Log(k)次合并即可。注意在进行log(k)时循环应该满足的条件。
这个循环体挺难写的：
思想：考虑奇偶情况，先把分支图画出来发现奇偶情况相同，然后再对每一次两两合并进行精准设置，在考虑一共要经过多少轮两两合并。
while interval < amount:
for i in range(0, amount - interval, interval * 2):
lists[i] = self.mergeTwoLists(lists[i], lists[i + interval])
interval *= 2代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#思路是将K个分解成k-1组两链表合并，时间复杂度是O(kn),n表示节点，k表示链表个数，空间复杂度为O(1)
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
q = dummy
p1 = l1
p2 = l2
while p1 and p2:
if p1.val <= p2.val:
q.next = p1
p1 = p1.next
else:
q.next = p2
p2 = p2.next
q = q.next
if p1:
q.next = p1
if p2:
q.next = p2
return dummy.next
if len(lists) == 0: #要注意这个lists=0的特殊情况
return None
k = len(lists) - 1
for ki in range(k):
lists[ki+1] = mergeTwoLists(lists[ki], lists[ki+1])
return lists[k]优化后的代码：进行Log(k)次合并即可，非常的省时
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
amount = len(lists)
if amount == 0:
return None
interval = 1
while interval < amount:
for i in range(0, amount - interval, interval * 2):
lists[i] = self.mergeTwoLists(lists[i], lists[i + interval])
interval *= 2
return lists[0] if amount > 0 else lists
def mergeTwoLists(self, l1, l2):
dummy = ListNode(0)
q = dummy
p1 = l1
p2 = l2
while p1 and p2:
if p1.val <= p2.val:
q.next = p1
p1 = p1.next
else:
q.next = p2
p2 = p2.next
q = q.next
if p1:
q.next = p1
if p2:
q.next = p2
return dummy.next
总结：做这道题最大的感触就是，（1）要学会分而治之的方法，复杂的K个链表合并问题分解成简单的合并2个链表的问题（2）要学会优化，从最初需要k-1次合并，变为log(k)次合并，时间复杂度大大降低。
【leetcode24两两交换链表中的节点】
题目：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
给定 1->2->3->4, 你应该返回 2->1->4->3.第一次做题：思路1：咋感觉自己越做题越大意了，要考虑特殊情况如奇偶链表和链表为空的情况，这道题其实就是一个断节点和连接节点的过程。代码如下面注释部分。
遇到的困难：1、对p.next=q（连接节点）不够熟悉，此时p指针不移动2、p = p.next 和p.next=p.next.next都对p指针移动了一次。3、奇偶链表的情况不同在while 循环的条件哪里有所体现。
第二次做题：思路2：设置三个指针prev,now,post，最后对post的情况进行讨论，关键在于翻转后的两个结点接下来如何连接下面结点的问题，在while循环内部，如果post和post.next同时存在，那么prev,now,post指针是都需要移动的，如果下面没有结点即post is None，那就连接post，同时退出循环；如果下面有一个结点即post在，post.next为空，接着连接post并且退出循环
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# dummy = ListNode(0)
# p = dummy
# p.next = head
# if head is None:
# return None
# q = p.next
# while q and q.next:#注意奇偶链表的情况
# p.next = q.next
# q.next = q.next.next
# p.next.next = q
# p = p.next.next
# q = q.next
# return dummy.next
if head is None or head.next is None:
return head
dummy = ListNode(0)
dummy.next = head
prev = head
now = prev.next
post = now.next
dummy.next = now
while now:
now.next = prev
if post and post.next:
prev.next = post.next
prev = post
now = prev.next
post = now.next
elif post:
prev.next = post
break
elif post is None:
prev.next = post
break
return dummy.next
总结1：分清楚链表的基本操作：连接节点，移动指针，考虑特殊情况。
总结2：三个指针，先考虑一般情况，后来主要考虑代码循环内部遇到的特殊情况，然后进行分支结构。
【leetcode25.K个一组翻转链表】
题目：
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路：递归法。先翻转前k个节点，然后递归。
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
#先解决前k个的翻转[a, b)，然后接上用递归
# 非递归法
def reverseab(head, end): #关键是左闭右开
pre = None
now = head
while now != end:
tmp = now.next
now.next = pre
pre = now
now = tmp
return pre
#递归法 翻转前N个节点
self.after = None
def reverseN(head, k):
if k == 1:
self.after = head.next
return head
last = reverseN(head.next, k - 1)
head.next.next = head
head.next = self.after
return last
def to_kth_node(head, k): #注意k-1 和不减的区别
# k -= 1
p = head
while k > 0 and p:
p = p.next
k -= 1
return p
q = head
m = k
while m > 0 and q:
q = q.next
m -= 1
if m > 0:
return head
node = to_kth_node(head, k)
# new_head = reverseab(head, node)
new_head = reverseN(head, k)
head.next = self.reverseKGroup(node, k)
return new_head
#整理：递归法翻转链表、非递归法翻转链表；翻转指定mn长度的链表、递归法非递归法；k个一组翻转链表，递归法。
#总结，pre,now非递归翻转指定mn长度的链表，注意这样好做[a,b);to_kth_node一开始不用k-=1。详解：
- to_kth_node函数很简单，请看如下代码就可以搞明白。
- reverse函数是核心，在reverse函数中，有三个指针分别为prev/now/post，其中prev/now是为了对相邻节点进行翻转，即now.next = prev,在这个操作后前面和post之间的链就断开了，而post就是起到一个找到（连接）后面节点继续操作的一个作用。需要注意两点，一是reverse对begin和end进行处理后，其实是一个相交链，像环一样，在reverseKGroup函数中要注意对now_end.next进行处理（和后面的节点相连接），即now.next=prev后，此时仍有prev.next=now，因此要对prev.next这条链也就是后面的now_end.next进行处理；二是当begin.next=end=now，虽然没进入循环，但是仍需要now.next=prev,别忘了。
- reverseKGroup函数是灵魂，首先在to_kth_node和reverse函数的基础上设置四个指针，now_begin/now_end/next_begin/next_end其中next_begin也是起到一个找到下面一组节点的作用。需要注意的是当next_end存在时，now_end.next = next_end，不存在时now_end.next = next_begin.
代码如下：
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: if head is None: return None if self.to_kth_node(head, k) is None: return head now_begin = head new_head = self.to_kth_node(head, k) now_end = self.to_kth_node(now_begin, k) next_begin = self.to_kth_node(now_begin, k+1) next_end = self.to_kth_node(next_begin, k) while now_begin and now_end: now_begin, now_end = self.reverse(now_begin, now_end) if next_end: now_end.next = next_end else: now_end.next = next_begin now_begin = next_begin now_end = self.to_kth_node(now_begin, k) next_begin = self.to_kth_node(now_begin, k+1) next_end = self.to_kth_node(next_begin, k) return new_head def to_kth_node(self, head, k): point = head k -= 1 while k > 0 and point: point = point.next k -= 1 return point def reverse(self, begin, end): #这个可不是完全相等的 if begin is end: #试试这可不可以写等号 return begin, end prev = begin now = prev.next post = now.next while post is not end.next: now.next = prev prev = now now = post post = post.next now.next = prev return end, begin #这个题主要是把reverse函数写出来，然后再把reverseKGroup函数写对。参考csdn总结。总结：通过这道题，深刻明白了节点间断链连接链的基本操作。在断链前一定要先找到下一节点，要不就找不到啦。
二次版本代码：思路较清楚
class Solution: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: if head is None or head.next is None: return head now_begin = head now_end = self.to_kth_node(head, k) if now_end is None: return head new_head = now_end next_begin = self.to_kth_node(head, k+1) next_end = self.to_kth_node(next_begin, k) while True: now_begin, now_end = self.reverse(now_begin, now_end) if next_end is None or next_begin is None: now_end.next = next_begin break now_end.next = next_end now_begin = next_begin now_end = next_end next_begin = self.to_kth_node(now_begin, k+1) next_end = self.to_kth_node(next_begin, k) return new_head def to_kth_node(self, head, k): k -= 1 point = head while k > 0 and point: point = point.next k -= 1 return point def reverse(self, begin, end): if begin is end: return begin, end prev = begin now = prev.next post = now.next while post is not end.next: now.next = prev prev = now now = post post = post.next now.next = prev return end, begin #这个题主要是把reverse函数写出来，然后再把reverseKGroup函数写对。参考csdn总结。这个版本注意一开始next_end不存在的情况，因为k可能大于整个链表的长度。
【leetcode61.旋转列表】
题目：给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL代码如下：
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def rotateRight(self, head: ListNode, k: int) -> ListNode: if head is None: return head length_link = self.length_of_link(head) if k % length_link == 0: return head p = head k_real = k % length_link left = self.to_kth_node(head, length_link-k_real) right = left.next end = self.to_kth_node(head, length_link) end.next = p left.next = None return right def to_kth_node(self, head, k): point = head k -= 1 while k > 0 and point: point = point.next k -= 1 return point # PrintList(to_kth_node(node1, 2)) def length_of_link(self, head): q = head i = 0 while q: q = q.next i += 1 return i # print(length_of_link(node1)) # PrintList(rotateRight(node1, 4))【leetcode83.删除列表中的重复元素】
题目：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
输入: 1->1->2 输出: 1->2
思路：设置三个指针，prev,now,p如果now.val和prev.val相等，那么prev.next = p，循环的条件是while p:,因此在p为空时跳出循环，需要再次判断prev和now是否相等，这一点很容易忽略，记得补充。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
dummy = head
prev = dummy
now = prev.next
p = now.next
while p:
if now.val == prev.val:
prev.next = p
now = p
p = p.next
else:
prev = now
now = now.next
p = p.next
if now.val == prev.val:
prev.next = None
return dummy
第二遍做的时候，用了两个指针prev和now，小心点，防止出错。
【leetcode82.删除排序链表中的重复元素 II】
题目：给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
思路：
- 建立两个指针pre和cur，最终想pre.next = cur
- 首先找到相同节点的入口，然后cur定位到第一个不是重复节点的值，循环直至没有cur.val == cur.next.val情况出现
- 令pre.next = cur
- 继续循环pre = cur，cur=cur.next，直至cur为空
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None:
return None
dummy = ListNode(0)
dummy.next = head #注意pre和cur一开始都指向dummy
pre = dummy
cur = pre
while cur:
pre = cur
cur = cur.next
while cur and cur.next and cur.val == cur.next.val:
tmp = cur.val
while cur and cur.val == tmp:
cur = cur.next
pre.next = cur
return dummy.next【Leetcode86.分隔链表】
题目：给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
思路：可以想象成把这个链表分成两个小链表，一个是全部小于x的节点组成的列表，一个是大于等于x的节点组成的列表，最后将两个小链表连接起来，就可以得到完整的链表。定义链表头节点为head1,head2，定义三个指针p在(head1链表)移动，q在(head2链表)移动，m在整个head大链表中移动。需要注意的地方一是当两个小链表有一个不存在时，直接返回存在的链表，二是当两个链表都存在时，注意避免死循环，让p.next和q.next都等于None。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
if head is None or head.next is None:
return head
m = head
head1 = None
head2 = None
while m:
if m.val < x:
if head1 is None:
head1 = m
p = head1
m = m.next
else:
p.next = m
p = m
m = m.next
else:
if head2 is None:
head2 = m
q = head2
m = m.next
else:
q.next = m
q = m
m = m.next
if head1 != None and head2 != None: #注意这里，要分情况讨论
l = p
p.next = None
q.next = None
l.next = head2
return head1
if head1 == None and head2:
return head2
if head2 == None and head1:
return head1总结：发现链表题，开头要注意特殊情况head,head.next是否是None，中间循环要注意（常规思路），最后结尾要注意特殊情况。
【leetcode92.翻转链表2】
题目：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
思路：这个比25题简单多了，但是思路不变，仍然设置两个函数to_kth_node()和reverse(),然后再分情况讨论，m=n时，不需要翻转；m=1时，now_end连接第n+1个节点，返回新的头节点now_begin；m>1时连接now_begin,now_end,返回head；需要注意的也是同25题一致，注意reverse处理后其实是相交链，需要对now_end.next进行处理。另外，将if head is None or head.next is None放在主函数中才有用呀！！！
代码如下：
def to_kth_node(head, k):
point = head
k -= 1
while k > 0 and point:
point = point.next
k -= 1
return point
def reverse(head, begin, end):
if begin is end:
return end, begin
prev = begin
now = prev.next
post = now.next
while end.next is not post and post:
now.next = prev
prev = now
now = post
post = post.next
now.next = prev #最后一步需要连接
return end, begin
def reverseBetween(head: ListNode, m: int, n: int):
if head is None or head.next is None:
return head
now_begin = to_kth_node(head, m)
now_end = to_kth_node(head, n)
end_next = now_end.next
now_begin, now_end = reverse(head, now_begin, now_end)
if m == n:
return head
if m == 1:
now_end.next = end_next #对now_end处理，防止死循环；end_next为原始end的后一个值
return now_begin #注意这个返回值
if m > 1:
now_left = to_kth_node(head, m-1)
now_left.next = now_begin
now_end.next = end_next
return head总结：
指针问题，简单的基本插入删除操作搞明白；在处理过程中出现next时考虑是否存在next；循环到最后一步是否符合题目需要做判断；跳出循环一般是while 条件不满足，还可以结合break跳出。