典型的三指针反转链表的题目 不多说了，都写在注释里了
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: if head.next == None or m == n: return head faker = ListNode('skt') faker.next = head index = 0 cur = faker while index < m - 1: index += 1 cur = cur.next # index == m - 1 # cur = 反转之前的那个节点 forward = cur cur = cur.next#第m个，待反转部分反转前的第一个节点 index += 1#index == m # 如果反转部分只有2个数 # 即forward->a(cur)->b->after_part # 需forward->b ->a->after_part # after_part = forward.next.next # forward.next = cur.next # forward.next.next = cur # cur.next = after_part if m == n - 1: after_part = cur.next.next#None forward.next = cur.next# forward.next.next = cur cur.next = after_part return faker.next # m < n - 1，反转部分至少有三个数，三指针 # 记录第一个cur为newtail newtail = cur#1 nex = cur.next#2 nexnex = nex.next#3 #after_part = nexnex.next index += 2#index -> 4 # 先将index += 2,使之为三指针中的最后一个位置 # 当index<=n的时候，不断执行下面的操作 # forward a ->b ->c ->d ->after_part # cur nex nexnex # nex.next = cur # forward a <-b c-> d-> after_part # cur nex nexnex # cur = nex # nex = nexnex # nexnex = nexnex.next # forward a <-b c-> d-> after_part # cur nex nexnex # index += 1#保证此时index仍然指向nexnex while index <= n: nex.next = cur#nex.next = 2 cur = nex#cur = 3 nex = nexnex#nex = 4 nexnex = nexnex.next index += 1 after_part = nexnex #直到 # forward a(newtail) <-b <-c d ->after_part # cur nex nexnex(index) forward.next = nex nex.next = cur newtail.next = after_part return faker.next