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

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 || m == n) return head;
//         int p = 0;
//         ListNode rs = new ListNode(-1); // dump
//         rs.next = head; // 建立连接
//         ListNode now = rs; // 用于遍历
//         LinkedList<Integer> stack = new LinkedList<>();
//         ListNode tmp = head; // tmp指向交换的前一节点
//         while (now != null) {
//             if (p == m - 1) {
//                 tmp = now;
//             } else if (p >= m && p <= n) {
//                 stack.push(now.val);
//             }
//             if (p == n) {
//                 while (!stack.isEmpty()) {
//                     tmp.next = new ListNode(stack.pop());
//                     tmp = tmp.next;
//                 }
//                 tmp.next = now.next;
//                 return rs.next;
//             }
//             now = now.next;
//             ++p;
//         }
//         return rs;
//     }
    
    // 法二：进阶(逐步将node右边的元素加到pre后面)
     public ListNode reverseBetween (ListNode head, int m, int n) {
         ListNode dummy = new ListNode(-1);  // 哑巴节点，指向链表的头部
         dummy.next = head;
         ListNode pre = dummy;  // pre 指向要翻转子链表的前驱节点
         for (int i = 1; i < m; ++i) {
             pre = pre.next;
         }
         ListNode node = pre.next; // 逐步将node右边的元素加到pre后面
         for (int i = m; i < n; ++i) {
             ListNode next = node.next;
             node.next = next.next;
             next.next = pre.next;
             pre.next = next;
         }
         return dummy.next;
     }
    
}