链表内指定区间反转

1.借助栈（先进后出）

借助栈达到反转的效果，时间复杂度：O（n），遍历所有结点；空间复杂度：O（n），借助了栈
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(m==n)//m等于n表示不用反转
            return head;
        ListNode p=head;
        ListNode res=new ListNode(0);//链表的头结点
        ListNode t=res;
        for(int i=1;i<m;i++){//添加不用反转的结点
            t.next=new ListNode(p.val);
            t=t.next;
            p=p.next;
        }
        Stack<ListNode> s1=new Stack<>();
        for(int i=m;i<=n;i++){//存入反转的结点
            s1.push(p);
            p=p.next;
        }
        while(!s1.empty()){//添加反转的结点
            ListNode temp=new ListNode(s1.pop().val);
            t.next=temp;
            t=t.next;
        }
        while(p!=null){//添加不用反转的结点
            t.next=new ListNode(p.val);
            t=t.next;
            p=p.next;
        }
        return res.next;
    }
}
2.直接进行反转
时间复杂度：O（n），遍历所有结点；空间复杂度：O（1）
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(m==n)//m等于n表示不用反转
            return head;
        ListNode res=new ListNode(0);//链表的头结点
        res.next=head;
        ListNode pre=res;//反转子链表的前驱结点
        for(int i=1;i<m;i++){//移动到要进行反转的部分
            pre=pre.next;
        }
        head=pre.next;//head移动到反转链表的头结点
        for(int i=m;i<n;i++){//进行反转
            //很像头插法，如第一个案例，其实第一趟就是让3指向2，类推
            ListNode next=head.next;
            head.next=next.next;
            next.next=pre.next;
            pre.next=next;
        }
        return res.next;
    }
}