原题92. 反转链表 II
和正常的反转区别在于指定了要反转的区间

递推可以用头插法 最后注意把反转区间的尾指针接回原区间
加一个空表头，把原本的头节点作为一般节点考虑，避免部分区间从头节点开始的情况

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 加一个空表头 可以避免一部分特殊情况 把原来的表头作为一般结点使用
        ListNode temp = new ListNode();
        temp.next = head;
        head = temp;

        int pos = 0;  // pos存当前位置数字索引 空表头为0
        // 使用头插法 head是(left-1)位置的结点 tail是left位置的结点
        ListNode posHead = temp, posTail = temp.next;
        while (pos <= right && temp != null) {  // 遍历到超过反转区间
            if (pos == left - 1) {  // 找到head和tail
                posHead = temp;
                posTail = temp.next;
                temp = temp.next;
            } else if (pos > left && pos <= right) {  // 头插法
                ListNode cur = temp.next;  // 先记录下一位节点的地址
                temp.next = posHead.next;  // 当前节点的下一位指向头的下一位
                posHead.next = temp;  // 头的下一位指向当前节点
                temp = cur;  // 更新当前节点到原本的下一个节点
            } else {
                temp = temp.next;  // 到反转区间前的正常遍历
            }
            pos++;  // 位置索引+1
        }

        posTail.next = temp;  // 最后把反转区间的末元素指向原区间的下一位
        return head.next;
    }
}

还有一种思路 把区间拎出来先反转 反转后再接回到原来的区间
接的方式就是left-1$\rightarrow$right$\rightarrow$left$\rightarrow$right+1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) return head;  // 只反转一个单位 不做处理

        ListNode temp = new ListNode(-1, head);  // 空表头
        head = temp;  // 更新head

        for (int i = 0; i < left - 1; i++) temp = temp.next;  // 找left-1位置

        // 记录反转区间前一位节点 pre前一个结点 cur当前要交换的节点
        ListNode posHead = temp, pre = null, cur = temp.next;
        for (int i = left; i <= right; i++) {
            temp = cur.next;  // 先记录下一个节点位置
            cur.next = pre;  // 当前节点的下一个节点指向上一个节点
            pre = cur;  // 更新上一个节点为当前节点
            cur = temp;  // 更新当前节点为原来的下一个节点
        }

        posHead.next.next = cur;  // posHead.next还是left位置 该位置反转后是区间尾 其下一位指向right+1
        posHead.next = pre;  // left-1的下一位应当是指向反转后的区间头 即right

        return head.next;
    }
}