// @Title: 反转链表 II (Reverse Linked List II)
// @Author: qisiii
// @Date: 2020-06-01 18:52:50
// @Runtime: 0 ms
// @Memory: 36.1 MB
// @comment: 
// @flag: 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode lr;
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m==1&&n==1) return head;
        int i=1;
        ListNode ll=null;
        ll=head;
        if(m==1){
        head=reverseList(ll,n-m);
        }else{
        
        while(i<m-1){
            i++;
            ll=ll.next; 
        }
      ll.next=reverseList(ll.next,n-m);
        }
        
        return head;
    }
     public ListNode reverseList(ListNode head,int n) {
        
            ListNode cur=head.next;
            ListNode next;
            ListNode temp;
            temp=head;
            head.next=null;
            while(n-->0){
                 
            next=cur.next;
            cur.next=head;
            head=cur;
            cur=next;
            }
            temp.next=cur;
            return head;
            
    }
}

// @Title: 反转链表 II (Reverse Linked List II)
// @Author: qisiii
// @Date: 2024-04-13 22:21:56
// @Runtime: 0 ms
// @Memory: 40.3 MB
// @comment: 
// @flag: 
/**
 * 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 result=head,leftNode=null,firstNode=null;
        int leftTemp=left;
        //leftNode是反转区域前一个
        while(leftTemp>1){
            leftNode=head;
            head=head.next;
            leftTemp--;
        }
        //firstNode是反转区域第一个，反转之后就是最后一个，他要接上非反转区域右部分
        firstNode=head;
        ListNode pre=null,next=null;
        right=right-left+1;
        while(right>0){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
            right--;
        }
        //非反转区域左接上反转区域
        if(leftNode!=null){
            leftNode.next=pre;
        }
        //反转区域接上非反转区域右
        if(firstNode!=null){
            firstNode.next=head;
        }
        if(left==1){
            return pre;
        }
        return result;
    }
}

// @Title: 反转链表 II (Reverse Linked List II)
// @Author: qisiii
// @Date: 2024-04-13 23:00:50
// @Runtime: 0 ms
// @Memory: 40.2 MB
// @comment: 
// @flag: 
/**
 * 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) {
        int leftOld=left;
        ListNode result=new ListNode(-1,head);
        ListNode pre=result;
        while(leftOld>1){
            pre=pre.next;
            leftOld--;
        }
        ListNode cur=pre.next,next;
        right=right-left;
        while(right>0){
            next=cur.next;
            cur.next=next.next;
            //这里不用next.next=cur的原因是cur是不变的，但是pre.next却是一直变的
            next.next=pre.next;
            pre.next=next;
            right--;
        }
        return result.next;
    }
}