92. 反转链表 II

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

解题思路：

可以将left和right之间节点的指针反转，即2->3->4反转为2<-3<-4，这样只需要将节点1的next指向节点4，节点2的next指向节点5，即right变为头，left变为尾。

curr表示当前正在处理的节点，prev表示curr的前驱，还需要额外记录2个关键节点：

1. beginPre：第left个节点的前驱
2. begin：第left个节点

依次将left到right之间的节点进行上面所述的链表反转，每次链表反转时令curr.next=prev，但此时，curr的后继节点会丢失，在反转之前，令next=curr.next。之后就可以将left到right之间的节点依次反转了：

1. pre=curr
2. curr=next：curr指向反转之前的后继节点
3. next=curr.next：current的后继
4. curr.next=prev：反转链表
5. count++(count记录已经处理到第i个节点，count==right时结束反转)

反转结束后，此时，curr节点就是第right个节点，next节点就是right的后继节点，令：

1. beginPrev.next=curr
2. begin.next=next

即可将反转后的链表与原链表链接上

AC代码：
 

/**
 * 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 dumpy = new ListNode();
        dumpy.next=head;
        ListNode pre = dumpy;
        ListNode curr = head;
        int count =1;
        while (count
            pre=curr;
            curr=curr.next;
            count++;
        }
 
        //left前面那一个节点
        ListNode beginPre =pre;
        //left节点
        ListNode begin = curr;
 
        //next记录当前节点的下一个节点
        ListNode next =curr.next;
        //从left节点开始，将后面的节点指向前面的节点
        while (count
            pre=curr;
            curr=next;
            next=curr.next;
            curr.next=pre;
            count++;
        }
 
        beginPre.next=curr;
        begin.next=next;
 
        return dumpy.next;
    }
}