leetcode 【链表反转II】

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

核心部分还是用普通链表反转的三指针法

注意几个坑点：
首先思路是直接遍历到第m个节点之前的m-1个节点，并记录该节点为pre，用于反转后接通反转后区间的新头结点。

当被反转的部分包括原链表头指针时，注意要将pre设为None，作为标志，反转结束后直接将反转区间的头结点设为结果链表的新头结点

设定一个被反转链表部分的第一个节点为last，表示该位置为反转之后的尾指针，该位置用于接入原链表的下一个结点

# 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==None or head.next==None or m==n:
            return head
        cnt=1
        tmp=head
        pre=None
        while cnt<m-1:#首先遍历到被反转部分的前一个指针
            tmp=tmp.next
            cnt+=1
        if m!=1:
            pre=tmp
            tmp=tmp.next
            cnt+=1
        l=None
        last=tmp
        while cnt<=n:#普通的三支针法反转链表
            r=tmp.next
            tmp.next=l
            l=tmp
            tmp=r
            cnt+=1
        last.next=r
        if pre==None:#若反转部分包括head，设定pre为空，设定翻转后的链表作为整个链表的新head
            head=l
        else:#否则将之前记录的Pre接入反转后的新头结点
            pre.next=l
        return head