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

/*
 * 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,或者是链表反转区间长度为1
        if(head == null || head.next == null || m == n){
            return head;
        }
        ListNode head0 = head;//链表反转区间左边界
        ListNode prep0 = head;//链表反转区间左边界的前驱节点，有可能为空指针
        int m0 = m-2;
        //当反转区间左边界大于2时，才会遍历链表
        while (m0>0){
            prep0 = prep0.next;
            m0--;
        }
        if(m == 1){//当反转区间左边界=1时，此时prep0=null,head0为链表头指针
            prep0 = null;
            head0 = head;
        }else {
            head0 = prep0.next;
        }

        ListNode head1 = head;//链表反转区间右边界
        ListNode prep1 = head;//链表反转区间右边界的前驱节点，不可能为空指针
        int n0 = n-2;
        while (n0>0){
            prep1 = prep1.next;
            n0--;
        }
        if(n == 1){//当反转区间右边界=1时，此时prep1=null,head1为链表头指针
            prep1 = null;
            head1 = head;
        }else {
            head1 = prep1.next;
        }
        ListNode tail = head1.next;  //链表反转区间右边界的后继节点，有可能为空指针
        ListNode prep = prep0;  //链表反转区间左边界的前驱节点（即prep0），有可能为空指针
        ListNode next = head0.next;  //保存当前节点的后继节点
        ListNode head0Temp = head0;  //保存head0节点,当链表反转时，head0会移动，指针指向发生变化
        while (head0 != tail){  //head0为反转链表区间的第一个节点
            next = head0.next;  //保存当前节点的后继节点
            head0.next = prep;  //实现链表方向反转
            prep = head0;  //前驱节点后移
            head0 = next;  //当前节点后移
        }
        if(m != 1){
            prep0.next = head1;
        }
        head0Temp.next = tail;  //链表反转区间左边界的后继节点为链表反转区间右边界的后继节点

        return m==1?prep:head;  //如果m==1,prep0为空指针，反转区间的有边界节点即为头指针；如果m!=1,头指针不变
    }
}