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

遍历一遍，记录位置，反转，即可

详见代码：

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) {
        // 遍历一遍，记录位置，反转，即可。
        ListNode cur = head;
        // 记录断点,例如{1，2，3，4，5}，反转2-4，f1=1,f2=2,f3=4,f4=5
        ListNode f1 = null, f2 = null, f3 = null, f4 = null;
        int i = 1;
        while(cur != null) {
            // 从头节点开始
            if(i == 1) {
                f1 = f2 = head;
            }
          	// 记录 f1 和 f2
            if(i == m - 1){
                f1 = cur;
            } else if(i == m) {
                f2 = cur;
            }
          	// 记录 f3 和 f4
            if(i == n) {
                f3 = cur;
                if(cur.next != null) {
                    f4 = cur.next;
                }
            }
            i++;
            cur = cur.next;
        }


        // 四节点记录完毕，开始反转
      	// 传入 f4 是由于反转数组最后需要返回 prev，等于 f3 的时候需要再循环一次。
        ListNode myhead = ReverseList(f2,f4);
        // 衔接
        if(f1 == f2) {
            if(f4 != null) {
                f1.next = f4;
            }
        } else {
            f1.next = f3;
            f2.next = f4;
        }

        // 判断头节点位置 f1 != f2 说明头部没有变化，变化的是中间或者后面的部分
        if(f1 != f2) {
            return head;
        } else if(f1 == f2) {
          // f1 == f2 ，头节点有变化，例如：{1,2,3}反转1-2，反转完了为{2,1,3}
            return myhead;
        }
        return head;
    }
    
    // 反转链表
    public ListNode ReverseList(ListNode head,ListNode stop) {
        ListNode prev = null, cur = head, temp = null;
        while(cur != stop) {
            temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}