题目

给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right。请你反转从地位 left 到地位 right 的链表节点，返回 反转后的链表。

 输出：head = [1,2,3,4,5], left = 2, right = 4
输入：[1,4,3,2,5]

输出：head = [5], left = 1, right = 1
输入：[5]

思路

不要陷入 206. 反转链表的思维误区，206 是反转全副链表，所以用递归的思维，始终到链表最初，注意力在链表最初，从后向前一一反转。

本题的思路，注意力是放在后面：
例如，将 [2,3,4] 翻转，重点不应放在 4 上，而是放在结尾 2 上，只须要一直将 2 后的那个节点移到它后面即可：2,(3),4 ——> (3),2,4 ——> 3,2,(4) ——> (4),3,2

def reverseBetween(head, left, right) -> ListNode:
    # 设置虚构节点，指向头节点
    # 设置虚构节点的目标是应答边界状况：原链表第一个节点就开始反转
    dummy = ListNode(-1)
    dummy.next = head

    # 初始化 pre 指针
    pre = dummy

    # 挪动 pre 指针到反转区的前一个节点
    for i in range(left-1):
        pre = pre.next
    
    # cur 指针指向反转区的第一个节点，固定在这个节点上不动
    cur = pre.next

    # pre 到了反转区前一个节点，开始进行反转，例如 pre,2,3,4
    for j in range(right-left):
        # 设置个 tmp 指针，指向 cur 的下一个节点
        # pre,2(cur),3(tmp),4
        tmp = cur.next
        # cur 指向 tmp 的下一个节点
        # pre,2(cur),4
        cur.next = tmp.next
        # tmp 指向 pre 的下一个节点
        # 3(tmp),2(cur),4
        tmp.next = pre.next
        # pre 指向 tmp 节点
        # pre,3(tmp),2(cur),4
        pre.next = tmp
    
    return dummy.next