LeetCode 25. k个一组翻转链表(Reverse Nodes in k-Group)
2024-09-05 07:08:30
题目描述
给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
解题思路
首先遍历整个链表得到总长度,然后每k个节点依次反转,每次保存当前节点反转后的首节点和尾节点,以便拼接上下k个节点的链表;在第一次反转后记录新链表的首节点;最后节点不足k个时,把上一次反转后链表的尾节点拼接到之后的节点。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *left = head, *right = head, *newHead = NULL;
int len = ;
while(right){
len++;
right = right->next;
}
if(len < k) return head;
right = head;
while(len >= k){
ListNode *node = right;
ListNode *h = right;
right = right->next;
for(int i = ; i < k-; i++){
ListNode *next = right->next;
right->next = node;
node = right;
right = next;
}
if(newHead == NULL) newHead = node;
else{
left->next = node;
left = h;
}
len -= k;
}
left->next = right;
return newHead;
}
};
最新文章
- 在Windows上安装Elasticsearch 5.0
- HTML5元素、属性和格式化
- 进阶版css的点滴
- Tomcat内存设置
- 41.使用Chipscope时如何防止reg_wire型信号被优化掉
- 为EF DbContext生成的实体添加注释(T5模板应用)[转]
- Android Linux自带iptables配置IP访问规则
- select option 下拉多选单选bootstrap插件使用总结
- Java学习之finally
- SDUT 2933-人活着系列Streetlights(最小生成树Kruskal+和理查德设置来实现)
- 从0开始整合SSM框架-1.mybatis
- jmeter生成html格式接口自动化测试报告
- Unity重置Animator到初始状态和重复播放同一个Animation
- 《常见排序算法--PHP实现》
- [c/c++] programming之路(29)、阶段答疑
- React创建组件的三种方式及其区别
- Reading CLR via c# 4th Edition
- 企业私有云部署im,视频服务
- @ArrayList剖析
- Redis实战(七)