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

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类
     */
     //本题难点：空指针问题和控制反转区间
     //可以加入头结点来解决反转区间的问题（主要是解决从head到n区间的问题）
     //思路：先找到反转区间的前一个结点和末尾的后一个结点，方便连接
     //然后对反转区间进行迭代头插法（注意控制次数），最后进行连接。
     //时间O（N），空间O（1）
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(m==n) {
            return head;
        }
        ListNode Head=new ListNode(-1);
        ListNode head1=Head;//分别记录区间的前一个，和末尾的后一个
        ListNode tail1=head;
        Head.next=head;
        int n1=n;
        int m1=m-1;
        while(m1>0) {
            head1=head1.next;
            m1--;
        }
        while(n1>0) {
            tail1=tail1.next;
            n1--;
        }
        ListNode head2=null;//反转区间的头结点
        //cur和tmp用来迭代
        ListNode cur=head1.next;
        ListNode tmp=cur;
        int num=n-m+1;
        while(num>0) {
            tmp=cur.next;
            if(head2==null) {
                head2=cur;
                cur.next=tail1;
            }
            else {
                cur.next=head2;
                head2=cur;
            }
            cur=tmp;
            num--;
        }
        if(head1!=null)
        head1.next=head2;
        return Head.next;
    }
}