链表3——链表中的节点每k个一组翻转
【摘要】 链表——链表中的节点每k个一组翻转
题目：
描述
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
数据范围： ， ，链表中每个元素都满足 1000
要求空间复杂度 ，时间复杂度
要求空间复杂度 ，时间复杂度
例如：
给定的链表是 1→2→3→4→5
对于 , 你应该返回 2→1→4→3→5
对于 , 你应该返回 3→2→1→4→5
思路：
part1:
先进行分段，将其分为k段，并判断最后一段是否满足k
part2:
定义2个指针
part3：
循环：将长度为k的每段中的节点进行翻转，即指针指向前一个
part4:
通过前一段的尾指针，将每一段进行拼接
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
//找到每次翻转的尾部
ListNode* tail = head;
//将tail遍历k次到尾部
for(int i=0; i < k; i++){
//如果尾部为控，即不足k，直接返回剩余的链表，不翻转
if(tail == NULL)
return head;
//tail继续后移
tail = tail->next;
}
//翻转时需要的前序和当前节点
ListNode* pre = NULL;
ListNode* cur = head;
//每k段里面都进行一个链表的翻转循环，直到到达当前段尾节点前
while(cur != tail) {
//对每个节点进行翻转
ListNode* temp = cur->next;
cur->next = pre;
//2个指针都进行后移
pre = cur;
cur = temp;
}
//将每个k段的链表进行连接，即当前尾指向下一段要翻转的链表
head->next = reverseKGroup(tail, k);
return pre;
}
};
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）