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

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类
     */
    //思路:
    //1、元素[1,m-1]入队
    //2、[m,n]入栈,出栈构造新的链表
    //3、新链表入队
    //4、[n+1,length]入队
    //5、出队构造最终链表
          public ListNode reverseBetween (ListNode head, int m, int n) {
        if(head==null)return null;
        if(m==n)return head;
        // write code here
        ListNode cur=head;
        Stack<ListNode>stack=new Stack<>();
        Queue<ListNode>queue=new LinkedList<>();
        int i=1;
        //1、先将元素[1,m-1]入队
        while(i<m){
            System.out.println(cur.val);
            queue.offer(cur);
            cur=cur.next;
            i++;
        }
        
        //2、元素[m,n]入栈
        while(i<=n){
            System.out.println(cur.val);
            stack.push(cur);
            cur=cur.next;
            i++;
        }
        //出栈,并连接,结果得到一个相反的链表
        ListNode partHead=stack.pop();
        ListNode cur2=partHead;
        while(!stack.isEmpty()){
            System.out.println(cur2.val);
            ListNode next=stack.pop();
            cur2.next=next;
            cur2=next;
        }
        cur2.next=null;
    //3、新链表入队
        ListNode cur3=partHead;
        while(cur3!=null){
            System.out.println(cur3.val);
            queue.offer(cur3);
            cur3=cur3.next;
        }
    //4、剩下元素入队
        while(cur!=null){
            System.out.println(cur.val);
            queue.offer(cur);
            cur=cur.next;
        }
    //5、出队构造最终链表
        ListNode newHead=queue.poll();
        ListNode cur4=newHead;
        
        while(cur4!=null){
            System.out.println(cur4.val);
            ListNode next=queue.poll();
            cur4.next=next;
            cur4=next;
        }
        return newHead;
    }
}

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类
     */
    //思路:
    //直接对[m,n]元素进行翻转，需要借助节点pre和next
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(head==null)return null;
        if(m==n)return head;
        // write code here
        ListNode cur=head,pre=null,next=cur.next;
        int i=1;//计数器
        //先移动到第m个元素处
        while(i!=m){
            System.out.println(cur.val);
            pre=cur;
            cur=cur.next;
            next=cur.next;
            i++;
            
        }
        //记录下m-1号元素和m号元素
        ListNode part1_tail=pre;
        ListNode part2_tail=cur;
        //翻转[m,n]间的元素
        while(i!=n){
            cur.next=pre;
            pre=cur;
            cur=next;
            next=cur.next;
            i++;
        }
        //将n号元素的next指向n-1号元素
        cur.next=pre;
        //综合可知一共有三部分链表：[1,m-1],[m,n],[n+1,end]
        //如果不存在第一部分，即part1_tail=null（或m=1），则只进行第二三部分的连接；
        //如果不存在第二部分，即m=n，则直接return head;
        //如果不存在第三部分，即cur=null（或n=end），则只进行第一二部分的连接；
        //如果存在第一部分：
        if(part1_tail!=null)
            //将m-1号元素的末尾连接到原第n号元素(现在是翻转后的第m个元素)
            part1_tail.next=cur;
        //不存在时，head直接就是第n号元素
        else
            head=cur;

        //不管第三部分存不存在，第二部分最后链接的都是n+1号元素（如果不存在则为null）
        //将翻转后的链表部分连接到第n+1号元素
        part2_tail.next=next;

        return head;
}
}