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

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) {
        // write code here
        //先遍历到要处理的位置,让prehead指向第一个要被反转的节点的前一个节点
        ListNode prehead = new ListNode(0);
        ListNode reverseHead = new ListNode(0);
        prehead.next = head;
        if(head.next == null) return head;
        reverseHead = prehead;
        for(int i=1;i<m;i++){
            prehead = prehead.next;
        }
        //已经遍历到链表尾部
        if(prehead.next == null) return head;
        if(prehead.next.next == null) return head;
        //从prehead的下一个节点开始反转，反转的次数等于n-m
        ListNode last,current,next;
        last = prehead.next;
        current = last.next;
        next = current.next;
        for(int i=0;i<n-m;i++){
            current.next = last;
            last = current;
            current = next;
            if(next != null ) next = next.next;
        }
        prehead.next.next = current;
        prehead.next = last;
        return reverseHead.next;
    }
}

这里需要两个节点来作为前置节点，一个作为head的前置节点，一个作为需要遍历的起始节点的前置节点。

反转的终止条件，首先反转的次数肯定是n-m，其次在next节点需要处理，防止在空指针调用。

根据m和n的范围，需要处理遍历的起始节点为链表末尾节点的情况。

需要处理链表只有一个节点的情况。