算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 反转链表 II，我们先来看题面：
https://leetcode-cn.com/problems/reverse-linked-list-ii/
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
题意
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
解题
https://www.cnblogs.com/techflow/p/13541281.html题解
这题的题意很直接，就是让我们翻转链表当中指定的部分，并且只能通过一次遍历完成。我们很容易想明白，通过m和n我们可以将链表分成三个部分：分别是m左侧的，m到n之间的也就是我们需要翻转的部分，以及n右侧的部分。当然这里可能存在一个特殊情况，m左侧和n的右侧都有可能没有元素，我们可以先忽略，先考虑最一般的情况。翻转链表我们最常用的方法就是先把[m, n]区间里的元素先存储起来，人工翻转了之后，再重新构建成一段链表，替换原链表对应的部分。但是很明显也可以发现，这样做是不符合题目要求的。因为我们存储元素遍历了链表一次，我们在构建链表的时候又遍历了一次，至少需要两次遍历才可以完成。那怎么样才能一次遍历完成链表的翻转呢？其实也很简单，我们只需要倒叙插入就好了。比如我们有这样一段链表，我们想要翻转其中2、3、4这三个节点：首先，我们从1开始，1是翻转之后的起始部分。我们先记录下1的位置，这里1指向2保持不变。对于2号节点我们需要记录下它的后继，这里我们用tmp记录2号节点的后继，也就是3号节点。之后我们将2号节点的后继置为None。再下一步，我们用tmp记录3号节点的后继，将3号节点的后继指向2号节点。最后，我们如法炮制，将4号节点的后继指向3号节点，将1号节点的后继指向4号节点，并且将2号节点的后继指向4号节点的原后继，也就是None。这样我们就完成了链表部分的翻转，其中的原理很简单，就是利用了链表遍历和插入时候的性质，每次将需要翻转部分元素的后继指向它们原本的前驱。这句话有些拗口，但是多读几遍也就理解了。这个思路非常简单，但是用代码实现却不容易，很容易写错。尤其是在赋值的时候，很容易搞错指针到底应该指向哪里，到底需要哪些临时变量。关于这些内容没有太好的办法，只能加强训练，提升自己的基本功。最后， 我们考虑一下特殊情况。题目当中的特殊情况有两种， 第一种是m=1，第二种是n=链表末尾。其中第二种不算是特殊情况，因为在链表当中末尾的元素也有后继，就是None。但是m=1的情况需要小心，因为m=1的时候，翻转部分是没有前驱的，稍稍有些不同。解决也很简单，我们单独特判一下这种情况，人为创建一个前驱节点即可。class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if m == n:
return head
pnt = head
# 移动m-2格，到达翻转部分的前驱节点
for i in range(m-2):
pnt = pnt.next
flag = False
# 特判m=1的情况，如果m=1那么人为制造一个节点作为前驱
if m == 1:
flag = True
pnt = ListNode(0)
pnt.next = head
head = pnt
# cur即当前待翻转的节点
cur = pnt.next
# pre表示cur的前驱
pre = pnt
# last表示最后一个翻转的元素
last = pnt.next
for i in range(m, n+1):
# 先记录下当前节点的后继
nxt = cur.next
# 将当前节点的后继指向前驱
cur.next = pre
pnt.next = cur
pre = cur
cur = nxt
# 将last指向翻转之后的元素，将链表串起来
last.next = cur
return head.next if flag else head
链表的相关操作非常考验基本功，虽然算法简单，但是对链表不熟悉，逻辑思考能力稍稍弱一些的同学想要做出这道题还是比较困难的。也因此，很多公司在面试的时候喜欢询问链表相关的操作和算法，以此考察候选人的基本功。如果想要进入大公司的，建议好好练习一下相关的问题，一定会有帮助的。好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
