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

42

编程题 42 /69

将给定的单链表 $\ L$ ： $L_0→L_1→…→L_{n-1}→L_ n$
重新排序为： $L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…$
要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

数据范围：链表长度 $0 \le n \le 20000$ ，链表中每个节点的值满足 $0 \le val \le 1000$

要求：空间复杂度 $O(n)$ 并在链表上进行操作而不新建链表，时间复杂度 $O(n)$

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

参考答案

先找到链表的中点，把后半部分逆序，然后使用两个指针同时向后移动，将后面的节点插入前面即可。

查看讨论

1
...
37
38
39
40
41
42
43
44
45
46
47
...
69
跳转到

上一题下一题

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

扫一扫，把题目装进口袋

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



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

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