NC21 链表内指定区间反转

题目链接：https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c

题目描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 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)

示例 1：

输入：{1,2,3,4,5},2,4
返回值：{1,4,3,2,5}

示例 2：

输入：{5},1,1
返回值：{5}

解题代码

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
        Stack<Integer> stack = new Stack<>();
        ListNode temp = head;
        int i = 1;
        // 指定范围入栈
        while (temp != null) {
            if (i >= m && i <= n) {
                stack.push(temp.val);
            }
            temp = temp.next;
            i++;
        }
        temp = head;
        i = 1;
        // 指定范围出栈
        while (temp != null) {
            if (i >= m && i <= n) {
                temp.val = stack.pop();
            }
            temp = temp.next;
            i++;
        }
        return head;
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2023/04/04 10:34:10