编程题 62 /71

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围： $\ 0 \le n \le 2000$ ， $1 \le k \le 2000$ ，链表中每个元素都满足 $0 \le val \le 1000$
要求空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

例如：

给定的链表是 $1\to2\to3\to4\to5$

对于 $k = 2$ , 你应该返回 $2\to 1\to 4\to 3\to 5$

对于 $k = 3$ , 你应该返回 $3\to2 \to1 \to 4\to 5$

参考答案

将一条链表分块分为链表长度/k块链表，如果处不尽则说明后面会有剩下的那一块是不满长度为k的。在最初的时候需要定义两个NodeList表示result(结果)和 now(当前所到达的结果链表的位置)。之后遍历块的长度，对每一个链表块进行翻转，再翻转完后将完成的链表插入到now链表的下一个，再将now链表更新到最前即可。

纠错收藏

查看讨论

1
...
57
58
59
60
61
62
63
64
65
66
67
...
71
跳转到

上一题下一题

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

扫一扫，把题目装进口袋

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



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

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