Leetcode92:反转链表II（区间反转链表）

一、题目

给你单链表的头指针 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]

left和right是索引，但是是从1开始（很无语，，，害我写了好多次才通过）

二、题解

思路：先找到left节点，再计算left到right中间的次数（就是要循环的次数），用3个指针：

• preHead：指向left索引的上一位（他的next用来连接要插入到left头的节点）
• pre：指向left索引
• cur：指向left索引的下一位（要把cur插入到头部（即PreHead.next）去）

每次让left后面的节点（cur指针指向的元素）插入到left前面（preHead指针的位置）。即头插法（可以看我上一篇文章的反转链表的第一种解法，只是这里不创建新的节点，而是直接改变前后节点的指针；头插法就是依次把后面的元素插入到第一位去，一直到right结束，那么当前区间的链表就逆序了）

比如head = [1,2,3,4,5], left = 2, right = 4：

• 3（cur指针指向的节点） 插入到2（pre指针指向的节点）的前面； [1,3,2,4,5]
• cur指针往后移动
• 4（cur指针指向的节点）插入到3（pre指针指向的节点）的前面： [1,4,3,2,5]

为了方便操作，设置一个虚拟头节点：
因为按照3个指针的写法，left位置前面是有一个节点的，但是如果要逆序的就是第一个和第二个，如果没有头节点，preHead就不存在了，就又要特殊处理。所以设置一个虚拟头节点让left不管是第一位还是第n位，都能走同样的逻辑。
第一遍：

第一遍.png

第二遍：

第二遍.png

class Solution {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }
        //创建一个虚拟头节点指向一开始的头节点
        ListNode dummy = new ListNode(-1,head);

        left = left - 1;
        right = right - 1;

        //要开始反转的节点的前一个节点
        ListNode preHead;
        head = dummy;
        //找到要翻转的起点 1->2->3->4->5->6
        //1->2->3->4->5->6 (2,4)
        for (int i = 0; i < left; i++) {
            head = head.next;
        }
        preHead = head;
        //反转的起点
        ListNode pre = preHead.next;
        // 要移动的节点
        ListNode cur = preHead.next.next;

        if (cur == null) {
            //链表只有两个节点 直接交换两个节点返回
            ListNode next = preHead.next;
            preHead.next = null;
            next.next = preHead;
            return next;
        }

        //要翻转的次数
        for (int j = 0; j < right-left; j++) {
             //暂存
            ListNode newHead = preHead.next;
            //暂存
            ListNode nextCur = cur.next; 

            pre.next = nextCur;
            preHead.next = cur;
            cur.next = newHead;

            //指针往前移动
            cur = nextCur;
        }
        return dummy.next;
    }
}
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}