力扣刷题TOP101：2.BM2 链表内指定区间反转
目录：
目的
思路
复杂度
记忆秘诀
python代码
目的
1 -> 2 -> 3 -> 4 -> 5→NULL,m=2,n=4 反转成 1→4→3→2→5→NULL
思路
这个任务是将链表的 第 m 到第 n 个节点反转，并让其他部分保持不变。想象你有一串项链，其中有一部分珠子（从第 m 颗到第 n 颗）被串反了，想把它恢复过来。我们需要 先把这部分珠子解下来，反转顺序，再重新串回去。
准备阶段：
-
添加假珠子起点
为了方便处理项链的开头，先在最前面加一颗“假珠子”，叫dummy，目的是避免处理链表头部特殊情况，保持代码的简洁。 -
找到prev的珠子
从dummy开始，数到第 m-1 个珠子的位置，这是反转区域的起点前一颗珠子。- 为什么要找到 m-1？ 因为你需要从这里开始操作，把后续的珠子重新串好。
开始修复：
锁定第 m 颗珠子和它后面的第 m+1 颗珠子
- 第 m 颗珠子叫
reverse_start，它是反转区域的第一个珠子。- 第 m+1 颗珠子叫
then，是反转过程中要插入到前面的珠子。逐步反转链子
在反转区域内，你一次反转一颗珠子，把它放到正确位置：
- 摘下
then珠子：把它从链子里取出。- 插到前面：把
then插到prev后面，变成反转区域的第一颗。- 更新指针：调整
prev的下一颗指向，把then继续往后推进。重复以上操作，直到把第 m 到 n 的珠子全部反转回来。
收尾阶段：恢复整条项链
-
连接两端
当反转完成后，前半部分的prev和后半部分的reverse_start都已经调整好，整条项链恢复顺序。 -
返回结果
最后返回dummy.next，它是修复好项链的真正起点。
复杂度
-
时间复杂度：O(n)
- 因为我们只需要遍历链表一次（找到位置并完成反转）。
-
空间复杂度：O(1)
- 只用了几个额外的指针来操作，不需要额外的存储空间。
记忆秘诀
假珠子起点：提供起点，避免麻烦。
找到前一颗
prev珠子：把修复的起点定下来。逐颗反转：摘下珠子，插到前面，逐步完成反转。
连接恢复：项链恢复。
python代码
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @param m int整型
# @param n int整型
# @return ListNode类
#
class Solution:
def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
# write code here
# 如果链表为空，或者 m 和 n 相等（即没有需要反转的区间），直接返回链表。
# 就像项链上没有需要反转的珠子时，什么都不做。
if not head or m == n:
return head
# 创建一个虚拟头节点，以简化处理
# 创建一个“假珠子” dummy，它指向链表的头节点。
dummy = ListNode(0)
dummy.next = head
# prev 现在指向假珠子（dummy）。这个珠子将帮助我们找到反转区间前一颗珠子的位置。
prev = dummy
# 找到 m-1 节点
# 从假珠子开始，循环 m-1 次，找到 第 m-1 颗珠子，记住它是反转区域的前一颗珠子
for _ in range(m - 1):
prev = prev.next
# 开始反转
# reverse_start 指向第 m 颗珠子，它是反转区域的第一个珠子；
reverse_start = prev.next # m 位置
# then 指向第 m+1 颗珠子，是反转过程中要插入到前面的位置。
then = reverse_start.next # m+1 位置
# 反转 m 到 n 的部分
for _ in range(n - m):
# 我们把珠子then从链表中摘下,要保留住 m 位置后面的珠子，确保链条不被断开
reverse_start.next = then.next # 保存 m 的下一个
# 然后将 then 插入到 prev 和 reverse_start 之间，这样就完成了反转的一步。
then.next = prev.next # 将 m+1 插入到 m 之前
# then 已经变成了新的 m 位置珠子，完成了插入
prev.next = then # 更新 prev 的 next
# 继续反转下一个珠子，直到我们完成所有反转
then = reverse_start.next # 更新 then 为下一个节点
# 因为 dummy.next 是新的链表头（即原链表的头部已经被修改过了）。
return dummy.next # 返回新的头节点
* 欢迎大家探讨新思路，能够更好的理解和记忆