链表进阶：反转链表 II

二、题目解析

题目的核心依然是反转链表。如果你还不熟悉如何反转一个单链表，请参看之前的文章 链表基本功：反转链表。

这道题目的关键点在于如何确定所要反转的区间。最简单，也是直接可以想到的就是通过遍历找到这个区间，然后对区间内的节点进行反转，最后把反转后的区间的头尾和链表的对应部分接起来。这里面有诸多细节，比如记录首尾，如何划定边界等等，这里我们先暂且不论，相信你自己去实现的时候你就能体会到这些点。我们这里只讨论思路。

这道题目最后跟进了一问，限制你只能遍历一次链表。也就是说，我们没有办法在进行区间反转之前就拿到区间的头尾，遍历和反转必须同时进行。这里的做法和之前没啥不同，只不过把之前的两件事情绑在一起做。

三、思路讲解

一开始我们创建两个指针，cur 指向的是当前节点，prev 指向的是前一个节点，按理来说，反转链表需要的是 3 个指针。但是我们现在还没确定边界，操作还没开始，所以第三个指针暂时还用不上。

另外就是我们有可能对头节点进行操作，需要这里创建了一个哨兵节点（这里就不解释了，不懂的话请参看之前的内容）。

当我们找到边界的时候，也就是当前指针指向了需要反转的第一个节点，表明我们可以进行反转操作了

在反转操作之前，我们需要记录两个节点位置

需要反转的链表的外边界节点 ( pre)

反转之后的末尾节点 ( tail)

需要反转的链表的外边界节点 ( pre)

反转之后的末尾节点 ( tail)

这两个指针仅仅是用来标记，在我们执行完区间反转操作之后，用来和其余的链表部分进行拼接。

然后就是执行链表反转了，这时就需要我们之前提到的 第三个指针

我们还是通过当前节点的位置和 right 进行比较来判断反转操作是否结束，结束的状态如下

改变之前标记的节点的 next 来达到拼接的目的

进行到这里，题目就算是完成了，最后返回哨兵节点的 next 就是我们的答案

四、动画演示

五、参考代码classSolution{

publicListNode reverseBetween(ListNode head, intleft, intright){

// 创建哨兵节点

ListNode dummy = newListNode;

dummy.next = head;

// 记录当前节点的位置（cur 指向的节点）

intcurPos = 1;

ListNode prev = dummy, cur = head;

// 找到左端点

for(; curPos < left; ++curPos) {

prev = cur;

cur = cur.next;

}

// 标记以方便操作完后进行拼接

ListNode pre = prev, tail = cur;

// 进行链表反转操作

for(; curPos