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

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 reverseBetween (ListNode head, int m, int n) {
        // write code here
        /* 边缘情况
            1. 空表
            2. 范围不合法， 不过好像题目中已经告诉了范围一定合法，所以不需要进行处理
        */
        if (head == null) return null;
        /*
            直接将 head 分成三部分
            注意 leftList 和 rightList 可能为空
            midList 必不为空
        */
        ListNode leftList = null;
        ListNode tailLeftList = null;
        ListNode midList = null;
        ListNode tailMidList = null;
        ListNode rightList = null;
        ListNode ptrCurHead = head;
        ListNode ptrNextHead = null;
        int index = 1;
        // 左侧有节点
        if (m > 1) leftList = head;
        // n 之后的都是rightList的部分
        while (index <= n) {
            ptrNextHead = ptrCurHead.next;
            if (index < m) { // 记录leftList的尾结点
                tailLeftList = ptrCurHead;
            } else { // midList
                if (index == m) { // 记录midList的尾结点
                    tailMidList = ptrCurHead;
                }
                ptrCurHead.next = midList;
                midList = ptrCurHead;
            }
            ptrCurHead = ptrNextHead;
            index++;
        }
        rightList = ptrCurHead;
        ListNode list = null;
	    // 拼接字符串 leftList(mayble null) + midList(must have node) + rightList(maybe null)  
        if (leftList != null)  {
            list = leftList;
            tailLeftList.next = midList;
        } else {
            list = midList;
        }
        if (rightList != null) {
            tailMidList.next = rightList;
        } else {
            tailMidList.next = null;
        }

        return list;
    } 
}