题解 | #链表内指定区间反转#

import java.util.*;
public class Solution {

    public ListNode reverseBetween (ListNode head, int m, int n) {
        
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        //1.走m-1步到left的前一个节点
        for(int i=0;i<m-1;i++){
            pre = pre.next;
        }
        //2.走n-m+1步到right节点
        ListNode rigthNode = pre;//当n=m=1时防止走出界
        for(int i=0;i<n-m+1;i++){
            rigthNode = rigthNode.next;
        }
        //3.截取出一个子链表
        ListNode leftNode = pre.next;
        ListNode cur = rigthNode.next;
 
        //4.切断链接
        pre.next=null;
        rigthNode.next=null;
 
        //5.反转局部链表
        reverse(leftNode);
 
        //6.接回原来的链表
        pre.next = rigthNode;
        leftNode.next = cur;

        return dummyNode.next;
    }

    private void reverse(ListNode s){
        //头插法反转链表
        ListNode cur = s;
        ListNode Cur_next = cur;
        while(cur!=null){
            //Cur_next 指向cur节点的下一个节点
            Cur_next = cur.next;
            cur.next = s;
            s = cur;
            cur = Cur_next ;
        }
    }
}