【算法面试必刷JAVA版二】链表内指定区间反转

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚
    
🚴🏻‍♂️个人主页：莫逸风
    
👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻
    
🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：BM2 链表内指定区间反转

描述：

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1→2→3→4→5→NULL, m=2,n=4
返回 1→4→3→2→5→NULL.

数据范围： 链表长度 0<size≤1000，0<m≤n≤size，链表中每个节点的值满足 |val| ≤1000

要求：时间复杂度 O(n)，空间复杂度 O(n)

进阶：时间复杂度 O(n)，空间复杂度 O(1)

思路：

方法一：利用栈，满足要求，简单易理解，这个就不画图解了。

将m-n的节点压入栈中再取出来，调整一下next指向就好了。

方法二：迭代，一次循环，没有栈直观，但不需要额外的空间，满足进阶要求，图解如下。

代码：

public class BM02 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(5);
        ListNode listNode4 = new ListNode(7);
        ListNode listNode5 = new ListNode(9);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode curListNode = listNode1;
        while (curListNode!=null){
            System.out.println(curListNode.val);
            curListNode = curListNode.next;
        }
        curListNode = reverseBetween2(listNode1,2,4);
        while (curListNode!=null){
            System.out.println(curListNode.val);
            curListNode = curListNode.next;
        }
    }

    /**
     * 方法二：迭代
     */
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode listNode = new ListNode(-1);
        listNode.next = head;
        ListNode pre = listNode;
        ListNode cur = head;
        for (int i = 1; i < m; i++) {
            pre = cur;
            cur = cur.next;
        }
        ListNode temp;
        for (int i = m; i < n; i++) {
            temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return listNode.next;
    }

    /**
     * 方法一：堆栈
     */
    public static ListNode reverseBetween2(ListNode head, int m, int n) {
        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode listNode = new ListNode(-1);
        listNode.next = head;
        ListNode cur = listNode;
        for (int i = 1; i < m; i++) {
            cur = cur.next;
        }
        ListNode pre = cur;
        cur = cur.next;
        for (int i = m; i <= n; i++) {
            stack.add(cur);
            cur = cur.next;
        }
        while (!stack.isEmpty()){
            pre.next = stack.pollLast();
            pre = pre.next;
        }
        pre.next = cur;
        return listNode.next;
    }
}

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101