题解 | #链表内指定区间反转# 笨办法加栈解决此问题

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
        if (head == null || head.next == null || n == m)
            return head;
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pmnode = head;
        Stack<ListNode> stack = new Stack<ListNode>();
        
        //找到第m个节点以及它前一个节点，注意如果m是第一个节点要单独处理，否则会报错
        if (m == 1) {
            pmnode = dummyNode;
        } else {
            for (int i = 1; i < m - 1; i++) {
                pmnode = pmnode.next;
            }
        }
        ListNode mnode = pmnode.next;
        
        //找到第m个节点以及它后一个节点
        ListNode nnode = mnode;
        for (int i = m; i < n; i++) {
            nnode = nnode.next;
        }
        ListNode rnnode = nnode.next;
        
        //入栈，注意循环条件
        while (mnode != nnode.next) {
            stack.push(mnode);
            mnode = mnode.next;
        }
        if (stack.isEmpty())
            return null;
        
        //出栈并反转链表
        ListNode head2 = stack.pop();
        ListNode temp = head2;
        while (!stack.isEmpty()) {
            temp.next = stack.pop();
            temp = temp.next;
        }
        
        //重新拼接链表
        temp.next = rnnode;
        pmnode.next = head2;
        return dummyNode.next;
    }
}