备考首页> 数据结构> 链表

50

编程题 50 /69

将一个节点数为 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)$

参考答案

先用两个指针找到区间的位置，再加入pre、next指针进行原地翻转。这样可以达成O(1)空间复杂度。如果用数组模拟的话即为O(n)空间复杂度。

查看讨论

1
...
45
46
47
48
49
50
51
52
53
54
55
...
69
跳转到

上一题下一题

扫描二维码，关注牛客网
意见反馈
下载牛客APP，随时随地刷题

扫一扫，把题目装进口袋

求职之前，先上牛客: 扫描二维码，进入QQ群



扫描二维码，关注牛客公众号

公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
牛客科技© All rights reserved admin@nowcoder.com
京ICP备14055008号-4 增值电信业务经营许可证营业执照人力资源服务许可证
京公网安备 11010502036488号