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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        
        if(head == null || head.next == null) return head;

        ListNode headPre = null, tailNext = null;

        ListNode pHead = head, rhead = null, pTail = head, rtail = null;

        int i = 1, j = 1;

        while(pHead != null){
            if(i == m){
                headPre = null;
                rhead = pHead;
                break;
            }else if(i + 1 == m){
                headPre = pHead;
                rhead = headPre.next;
                break;
            }else{
                pHead = pHead.next;
                i++;
            }
        }

        while(pTail != null){
            if(j == n){
                tailNext = pTail.next;
                rtail = pTail;
                break;
            }else if(j + 1 == n){
                rtail = pTail.next;
                tailNext = rtail.next;
                break;
            }else{
                pTail = pTail.next;
                j++;
            }
        }

        if(headPre != null){
            headPre.next = null;
        }
        rtail.next = null;

        ListNode newReverseListTail = rhead;
        ListNode newReverseListHead = reverseChainList(rhead);

        if(headPre != null){
           headPre.next = newReverseListHead;
        }else{
            head = newReverseListHead;
        }

        newReverseListTail.next = tailNext;

        return head;
    }

    public ListNode reverseChainList(ListNode head){

        if(head == null || head.next == null) return head;

        ListNode tail = head.next, pHead = head.next;

        //断开头节点，独立后面的链表
        head.next = null;

        //反转后面的链表
        pHead = reverseChainList(pHead);

        //把头节点跟新的尾链表连接上
        tail.next = head;
        tail = head;
        head = pHead;

        return head;
    }
}