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

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
	  //保存区间前的数据
        ArrayList<Integer> begin=new ArrayList<>();
	  //保存区间数据
        ArrayList<Integer> mid=new ArrayList<>();
	  //保存区间后的数据
        ArrayList<Integer> end=new ArrayList<>();
	  //用来反正区间的数据
        Stack<Integer> stack=new Stack<>();
        ListNode find=head;
        int i=1;
	  //初始化begin、mid、end集合数值
        while(find!=null){
		  //小于m添加到begin集合
            if(i<m){
                begin.add(find.val);
            }
		  //在m、n区间添加到栈用来反转
            if(i>=m&&i<=n){
                stack.push(find.val);
            }
		  //大于n添加到end集合
            if(i>n){
                end.add(find.val);
            }
            i++;
            find=find.next;
        }
	  //反转完成添加到mid集合
        while(!stack.isEmpty()){
            mid.add(stack.pop());
        }
	  //将begin、mid、end集合合并
        begin.addAll(mid);
        begin.addAll(end);
        i=1;
	  //生成链表
        Integer first=begin.get(0);
        ListNode tmp=new ListNode(first);
        ListNode returnList=tmp;
        for(Integer num:begin){
            if(i==1){
                i++;
                continue;
            }
            ListNode tmpNode=new ListNode(num);
            tmp.next=tmpNode;
            tmp=tmp.next;
        }
        return returnList;
    }
}