# 0092. Reverse Linked List II
Link: https://leetcode-cn.com/problems/reverse-linked-list-ii/
###### tags: `Leetcode` `Medium` `Linked List`
## 思路
### 思路一
### 两次遍历
思路如下：
* 加上虚拟头节点：方便操作
* 把要反转的链表的前一个和后一个节点记录下来
* 把反转链表从原链表中分离出来
* 反转
* 连接
### 思路二
### 一次遍历，穿针引线
整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。

下面我们具体解释如何实现。使用三个指针变量 ```pre```、```curr```、```next``` 来记录反转的过程中需要的变量，它们的意义如下：
* ```curr```：指向待反转区域的第一个节点 ```left```；
* ```next```：永远指向 ```curr``` 的下一个节点，循环过程中，```curr``` 变化以后 ```next``` 会变化；
* ```pre```：永远指向待反转区域的第一个节点 ```left``` 的前一个节点，在循环过程中不变。

第 1 步，我们使用 ①、②、③ 标注「穿针引线」的步骤。

操作步骤：
* 先将 ```curr``` 的下一个节点记录为 ```next```；
* 执行操作 ①：把 ```curr``` 的下一个节点指向 ```next``` 的下一个节点；
* 执行操作 ②：把 ```next``` 的下一个节点指向 ```pre``` 的下一个节点；
* 执行操作 ③：把 ```pre``` 的下一个节点指向 ```next```。

拉直后

## Code

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        // 注意：切断链接
        pre.next = null;
        rightNode.next = null;

        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步：接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }

    private void reverseLinkedList(ListNode head) {
        // 也可以使用递归反转一个链表
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }
}

第二步