题目描述

给出一个链表,每 个节点一组进行翻转,并返回翻转后的链表。

是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 的整数倍,那么将最后剩余节点保持原有顺序。

示例 :

给定这个链表:1->2->3->4->5

当 = 2 时,应当返回: 2->1->4->3->5

当 = 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;
}
};

最新文章

  1. 在Windows上安装Elasticsearch 5.0
  2. HTML5元素、属性和格式化
  3. 进阶版css的点滴
  4. Tomcat内存设置
  5. 41.使用Chipscope时如何防止reg_wire型信号被优化掉
  6. 为EF DbContext生成的实体添加注释(T5模板应用)[转]
  7. Android Linux自带iptables配置IP访问规则
  8. select option 下拉多选单选bootstrap插件使用总结
  9. Java学习之finally
  10. SDUT 2933-人活着系列Streetlights(最小生成树Kruskal+和理查德设置来实现)
  11. 从0开始整合SSM框架-1.mybatis
  12. jmeter生成html格式接口自动化测试报告
  13. Unity重置Animator到初始状态和重复播放同一个Animation
  14. 《常见排序算法--PHP实现》
  15. [c/c++] programming之路(29)、阶段答疑
  16. React创建组件的三种方式及其区别
  17. Reading CLR via c# 4th Edition
  18. 企业私有云部署im,视频服务
  19. @ArrayList剖析
  20. Redis实战(七)

热门文章

  1. 用表格制作商品购买页面--(table)
  2. span元素
  3. [LeetCode] 40. Combination Sum II ☆☆☆(数组相加等于指定的数)
  4. 认识Caffe与Caffe2
  5. celery的简单使用
  6. python dict list 遍历的几种常见方法
  7. new函数
  8. 关于swap交换操作的新方法
  9. Sklearn分类树在合成数集上的表现
  10. 我带旅游ERP管理系统开发的经历