咸宁网站建设公司,如何建微信微商城网站,网站 续费,软件开发是学什么原题链接
难度#xff1a;hard\color{red}{hard}hard
题目描述
给你链表的头节点 headheadhead #xff0c; kkk 个节点一组进行翻转#xff0c;请你返回修改后的链表。 kkk 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节点总数不是 kkk 的整数倍#xf…原题链接
难度hard\color{red}{hard}hard
题目描述
给你链表的头节点 headheadhead kkk 个节点一组进行翻转请你返回修改后的链表。
kkk 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 kkk 的整数倍那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。
示例 1 输入head [1,2,3,4,5], k 2
输出[2,1,4,3,5]
复制示例输入示例 2 输入head [1,2,3,4,5], k 3
输出[3,2,1,4,5]
复制示例输入提示
链表中的节点数目为 nnn1kn50001 k n 50001kn50000Node.val10000 Node.val 10000Node.val1000
进阶 你可以设计一个只用 O(1)O(1)O(1) 额外内存空间的算法解决此问题吗 算法
(模拟)
增加虚拟头结点 dummy。对于每一轮的修改求出 end 指针为下一轮需要交换的最后一个结点在找 end 的过程中若不足 k 个结点则直接终止循环。在找到 end 后设置 a 和 b 两个指针修改相邻结点之间的连接关系需要一个临时的 c 指针来指向 b 的 next。参考代码最终修改 p-next 和 c-next。令 p 指向下一轮修改的起始位置的前一个位置。 C 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummy new ListNode(0, head);for (auto p dummy;;) {auto end p;for (int i 0; i k end ! NULL; i ) end end-next;if (end NULL) break;auto a p-next, b a-next;for (int i 0; i k - 1; i ) {auto c b-next;b-next a;a b, b c;}auto c p-next;p-next a, c-next b;p c;}return dummy-next;}
};
