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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseListNode(ListNode head){
        ListNode cur = head;
        ListNode pre = null;
        while(cur!=null){
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }
    public ListNode reverseBetween (ListNode head, int m, int n) {
        
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        //找到反转区间头节点与头.pre节点
        ListNode reverseHead = dummyHead.next;
        ListNode pre = dummyHead;
        for (int i = 1; i < m; i++) {
            pre = reverseHead;
            reverseHead = reverseHead.next;
        }

        //找到反转区间尾节点与尾.next节点
        ListNode reverseTail = reverseHead;
        for (int i = m; i < n; i++) {
            reverseTail = reverseTail.next;
        }

        //先保存后斩断
        ListNode reverseTailNext = reverseTail.next; 
        reverseTail.next = null;

        //反转
        pre.next = reverseListNode(reverseHead);

        //接上
        reverseHead.next = reverseTailNext;


        return dummyHead.next;
    }
}