NC21 链表内指定区间反转

  算法   3分钟   698浏览   0评论

NowCoder

题目链接：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

如果你觉得文章对你有帮助，那就请作者喝杯咖啡吧☕
微信
支付宝
😀
😃
😄
😁
😆
😅
🤣
😂
🙂
🙃
😉
😊
😇
🥰
😍
🤩
😘
😗
☺️
😚
😙
🥲
😋
😛
😜
🤪
😝
🤑
🤗
🤭
🫢
🫣
🤫
🤔
🤨
😐
😑
😶
😏
😒
🙄
😬
😮‍💨
🤤
😪
😴
😷
🤒
🤕
🤢
🤮
🤧
🥵
🥶
🥴
😵
😵‍💫
🤯
🥳
🥺
😠
😡
🤬
🤯
😈
👿
💀
☠️
💩
👻
👽
👾
🤖
😺
😸
😹
😻
😼
😽
🙀
😿
😾
👋
🤚
🖐️
✋️
🖖
🫱
🫲
🫳
🫴
🫷
🫸
👌
🤌
🤏
✌️
🤞
🫰
🤟
🤘
🤙
👈️
👉️
👆️
🖕
👇️
☝️
🫵
👍️
👎️
✊️
👊
🤛
🤜
👏
🙌
👐
🤲
🤝
🙏
✍️
💅
🤳
💪
🦾
🦿
🦵
🦶
👂
🦻
👃
👶
👧
🧒
👦
👩
🧑
👨
👩‍🦱
👨‍🦱
👩‍🦰
👨‍🦰
👱‍♀️
👱‍♂️
👩‍🦳
👨‍🦳
👩‍🦲
👨‍🦲
🧔‍♀️
🧔‍♂️
👵
🧓
👴
👲
👳‍♀️
👳‍♂️
🧕
👮‍♀️
👮‍♂️
👷‍♀️
👷‍♂️
💂‍♀️
💂‍♂️
🕵️‍♀️
🕵️‍♂️
👩‍⚕️
👨‍⚕️
👩‍🌾
👨‍🌾
👩‍🍳
👨‍🍳
🐶
🐱
🐭
🐹
🐰
🦊
🐻
🐼
🐨
🐯
🦁
🐮
🐷
🐸
🐵
🐔
🐧
🐦
🦅
🦉
🐴
🦄
🐝
🪲
🐞
🦋
🐢
🐍
🦖
🦕
🐬
🦭
🐳
🐋
🦈
🐙
🦑
🦀
🦞
🦐
🐚
🐌
🦋
🐛
🦟
🪰
🪱
🦗
🕷️
🕸️
🦂
🐢
🐍
🦎
🦖
🦕
🐊
🐢
🐉
🦕
🦖
🐘
🦏
🦛
🐪
🐫
🦒
🦘
🦬
🐃
🐂
🐄
🐎
🐖
🐏
🐑
🐐
🦌
🐕
🐩
🦮
🐕‍🦺
🐈
🐈‍⬛
🐓
🦃
🦚
🦜
🦢
🦩
🕊️
🐇
🦝
🦨
🦡
🦫
🦦
🦥
🐁
🐀
🐿️
🦔
🌵
🎄
🌲
🌳
🌴
🌱
🌿
☘️
🍀
🎍
🎋
🍃
🍂
🍁
🍄
🌾
💐
🌷
🌹
🥀
🌺
🌸
🌼
🌻
🌞
🌝
🌛
🌜
🌚
🌕
🌖
🌗
🌘
🌑
🌒
🌓
🌔
🌙
🌎
🌍
🌏
🪐
💫
⭐
🌟
✨
⚡
🔥
💥
☄️
☀️
🌤️
⛅
🌥️
🌦️
🌧️
⛈️
🌩️
🌨️
❄️
☃️
⛄
🌬️
💨
💧
💦
☔
🌊
🍇
🍈
🍉
🍊
🍋
🍌
🍍
🥭
🍎
🍏
🍐
🍑
🍒
🍓
🥝
🍅
🥥
🥑
🍆
🥔
🥕
🌽
🌶️
🥒
🥬
🥦
🧄
🧅
🍄
🥜
🍞
🥐
🥖
🥨
🥯
🥞
🧇
🧀
🍖
🍗
🥩
🥓
🍔
🍟
🍕
🌭
🥪
🌮
🌯
🥙
🧆
🥚
🍳
🥘
🍲
🥣
🥗
🍿
🧈
🧂
🥫
🍱
🍘
🍙
🍚
🍛
🍜
🍝
🍠
🍢
🍣
🍤
🍥
🥮
🍡
🥟
🥠
🥡
🦪
🍦
🍧
🍨
🍩
🍪
🎂
🍰
🧁
🥧
🍫
🍬
🍭
🍮
🍯
🍼
🥛
☕
🍵
🍶
🍾
🍷
🍸
🍹
🍺
🍻
🥂
🥃
🥤
🧃
🧉
🧊
🗺️
🏔️
⛰️
🌋
🏕️
🏖️
🏜️
🏝️
🏞️
🏟️
🏛️
🏗️
🏘️
🏙️
🏚️
🏠
🏡
🏢
🏣
🏤
🏥
🏦
🏨
🏩
🏪
🏫
🏬
🏭
🏯
🏰
💒
🗼
🗽
⛪
🕌
🛕
🕍
⛩️
🕋
⛲
⛺
🌁
🌃
🏙️
🌄
🌅
🌆
🌇
🌉
🎠
🎡
🎢
💈
🎪
🚂
🚃
🚄
🚅
🚆
🚇
🚈
🚉
🚊
🚝
🚞
🚋
🚌
🚍
🚎
🚐
🚑
🚒
🚓
🚔
🚕
🚖
🚗
🚘
🚙
🚚
🚛
🚜
🏎️
🏍️
🛵
🦽
🦼
🛺
🚲
🛴
🛹
🚏
🛣️
🛤️
🛢️
⛽
🚨
🚥
🚦
🚧
⚓
⛵
🛶
🚤
🛳️
⛴️
🛥️
🚢
✈️
🛩️
🛫
🛬
🪂
💺
🚁
🚟
🚠
🚡
🛰️
🚀
🛸
🧳
⌚
📱
💻
⌨️
🖥️
🖨️
🖱️
🖲️
💽
💾
📀
📼
🔍
🔎
💡
🔦
🏮
📔
📕
📖
📗
📘
📙
📚
📓
📒
📃
📜
📄
📰
🗞️
📑
🔖
🏷️
💰
💴
💵
💶
💷
💸
💳
🧾
✉️
📧
📨
📩
📤
📥
📦
📫
📪
📬
📭
📮
🗳️
✏️
✒️
🖋️
🖊️
🖌️
🖍️
📝
📁
📂
🗂️
📅
📆
🗒️
🗓️
📇
📈
📉
📊
📋
📌
📍
📎
🖇️
📏
📐
✂️
🗃️
🗄️
🗑️
🔒
🔓
🔏
🔐
🔑
🗝️
🔨
🪓
⛏️
⚒️
🛠️
🗡️
⚔️
🔫
🏹
🛡️
🔧
🔩
⚙️
🗜️
⚗️
🧪
🧫
🧬
🔬
🔭
📡
💉
🩸
💊
🩹
🩺
🚪
🛏️
🛋️
🪑
🚽
🚿
🛁
🧴
🧷
🧹
🧺
🧻
🧼
🧽
🧯
🛒
🚬
⚰️
⚱️
🗿
🏧
🚮
🚰
♿
🚹
🚺
🚻
🚼
🚾
🛂
🛃
🛄
🛅
⚠️
🚸
⛔
🚫
🚳
🚭
🚯
🚱
🚷
📵
🔞
☢️
☣️
❤️
🧡
💛
💚
💙
💜
🖤
💔
❣️
💕
💞
💓
💗
💖
💘
💝
💟
☮️
✝️
☪️
🕉️
☸️
✡️
🔯
🕎
☯️
☦️
🛐
⛎
♈
♉
♊
♋
♌
♍
♎
♏
♐
♑
♒
♓
🆔
⚛️
🉑
☢️
☣️
📴
📳
🈶
🈚
🈸
🈺
🈷️
✴️
🆚
💮
🉐
㊙️
㊗️
🈴
🈵
🈹
🈲
🅰️
🅱️
🆎
🆑
🅾️
🆘
❌
⭕
🛑
💢
💯
💠
♨️
🚷
🚯
🚳
🚱
🔞
📵
🚭
❗
❕
❓
❔
‼️
⁉️
🔅
🔆
🔱
⚜️
〽️
⚠️
🚸
🔰
♻️
✅
🈯
💹
❇️
✳️
❎
🌐
💠
Ⓜ️
🌀
💤
🏧
🚾
♿
🅿️
🈳
🈂️
🛂
🛃
🛄
🛅
  0 条评论