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

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) {
        // 1. 处理特殊情况：只有一个节点或者为空或者m=n
        if (head == null || head.next == null || m == n) return head;
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();

        // 2. 将前m-1个存入栈s1中
        int M = m;
        ListNode cur = head;
        while (M-- != 1) {
            s1.push(cur);
            cur = cur.next;
        }

        // 3. 将m到n的节点存入栈s2
        int count = n - m + 1;
        while (count-- != 0) {
            s2.push(cur);
            cur = cur.next;
        }

        // 4. 将中间需要反转的部分使用栈反转
        ListNode newHead = new ListNode(-1);
        ListNode tmp1 = newHead;
        ListNode top = null;
        while (!s2.empty()) {
            top = s2.pop();
            tmp1.next = top;
            tmp1 = tmp1.next;
        }

        // 此处反转完成
        tmp1.next = cur;

        // 5. 处理前m-1个节点（将栈s1中的元素存入栈s2，然后再从s2依次取出保证了原有顺序）
        while (!s1.empty()) {
            s2.push(s1.pop());
        }

        ListNode newHead2 = new ListNode(-1);
        tmp1 = newHead2;
        while(!s2.empty()) {
            top = s2.pop();
            tmp1.next = top;
            tmp1 = tmp1.next;
        }
  
        // 6. 返回整理后的
        tmp1.next = newHead.next;
        return newHead2.next;
    }
}