首页 > 试题广场 >

链表内指定区间反转

[编程题]链表内指定区间反转

热度指数：445075 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：链表长度 $0 < size \le 1000$ ， $0 < m \le n \le size$ ，链表中每个节点的值满足 $|val| \le 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}

示例3

输入

{1,2,3,4},1,4

输出

{4,3,2,1}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

堆栈哲学

发表于 2021-07-11 16:05:39

精华题解解法一：双指针(两次遍历) 思路步骤：要反转局部链表，可以将该局部部分当作完整链表进行反转再将已经反转好的局部链表与其他节点建立连接，重构链表建议使用虚拟头节点的技巧，可以避免对头节点复杂的分类考虑，简化操作。反转前后图示：配图说明：反转步骤： Java参考代码：展开全文

牛客题解官

发表于 2022-04-22 10:59:30

精华题解题目的主要信息：将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转链表其他部分不变，返回头节点举一反三：学习完本题的思路你可以解决如下题目： BM1.反转链表 BM3.链表中的节点每k个一组翻转方法一：头插法迭代（推荐使用）思路：在学会了BM1.反转链表之后，要解决展开全文

认认真真coding

发表于 2021-07-15 10:38:29

精华题解题目描述将一个链表m位置到n位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度O(1)。例如：给出的链表为 1→2→3→4→5→NULL, m=2,n=4返回1→4→3→2→5→NULL.注意：给出的m,n满足以下条件：1≤m≤n≤链表长度（参考杭电 De梦的题解）方法一：直接暴力求解求展开全文

漫漫云天自翱翔

发表于 2021-07-16 01:57:14

精华题解题解一：迭代翻转题解思路：建立一个空白节点指向头节点，然后翻转[m,n]内的节点。参数分析：　ｐ：指向ｍ前一个节点，ｑ指向第ｎ个节点。ｐ１，ｐ２用于翻转．图示：复杂度分析：时间复杂度：O（Ｎ），最多遍历整个链表空间展开全文

南七技校

发表于 2021-07-29 18:32:10

其实我以前还是挺怕做链表的题目的，但是熟能生巧之后还是会理解一些，不要怕指针太多弄的自己搞不清楚在干什么；首先还是制造一个哨兵伪节点来避免头节点的分类讨论然后找到反转节点前一个位置的节点用pre指过去再者，就是运用头插法来反转链表了，pre后面是cur，这里需要不断地把cur后面的节点移动到p 展开全文