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

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
                // 1. 考虑错误情况：m > n 时候，返回null
        if (m > n) {
            return null;
        }
                // 2. 考虑不变情况：m == n 时候，返回head
        if (m == n) {
            return head;
        }
        // 3. 按m值寻找对应结点
        ListNode mHead = head;    // mHead记录第m个结点
        ListNode mHeadPre = null;    // mHeadPre记录第m个结点的前一个结点，为拼接链表做准备
        for (; m > 1; m--) {
            mHeadPre = mHead;
            mHead = mHead.next;
        }
        // 4. 按n值寻找对应结点
        ListNode nTail = head;    // nTail记录第n个结点
        for (; n > 1; n--) {
            nTail = nTail.next;
        }
        ListNode nTailNext = nTail.next;    // nTailNext记录第n个结点的下一个结点，为拼接链表做准备
        nTail.next = null;    // 将nTail.next 置为 null，为反转 mHead 和 nTail 之间的结点做准备         
        
        // 5. 将 mHead 和 nTail 之间的元素反转
        ListNode pre = null;
        ListNode cur = mHead;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        
        // 6. 拼接三个链表
        mHead.next = nTailNext;
        if (mHeadPre != null) {
            mHeadPre.next = nTail;
            return head;
        }else {
            return nTail;
        }
        
    }
}