天津建设工程信息网登录不了,东莞网站建设优化东莞,全国建筑行业资质查询平台,网站建设唯美谷网站25. K 个一组翻转链表 - 力扣#xff08;LeetCode#xff09;
一、题目要求
给你链表的头节点 head #xff0c;每 k 个节点一组进行翻转#xff0c;请你返回修改后的链表。
k 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍#x…25. K 个一组翻转链表 - 力扣LeetCode
一、题目要求
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。
k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。 示例 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]提示
链表中的节点数目为 n1 k n 50000 Node.val 1000 进阶你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗 二、解法1-双层递归 O(N) 进阶 这个题与翻转链表(每日一练反转链表-CSDN博客)类似但是它是分成了几个组分别进行反转反转链表时我们使用递归来完成这个题我们很容易想到把链表分层几部分分别递归但是难点在于各个部分反转后还需要进行连接这就又需要一层递归即 先递归(外层递归)到最后一个要进行反转的部分进行递归反转(内层递归)后得到它的新头后返回上一层递归(外层递归)上一层递归是前一个要进行反转的部分这部分又进行递归反转后将新尾连接到上一次返回的新头即可 新头就是旧尾要返回给调用它的上一次函数也就是链表的前一部分。 新尾就是旧头我们可以在外层递归时保存这个节点得到后一部分的新头后指向它。 外层递归是为了以从后向前的顺序枚举到所有需要反转的组 内存递归就是为了翻转这些组
class Solution {ListNode* __reverseKGroup(ListNode* last, ListNode* cur, int k) { // 内层递归if (k K){cur-next last;return cur;}ListNode* newhead __reverseKGroup(cur, cur-next, k1);cur-next last;return newhead; // 返回新头}ListNode* _reverseKGroup(ListNode* cur, ListNode* head, int k) { // 外层递归if (cur nullptr || cur-nextnullptr k ! K){return head;}if (k K){ListNode* head_next _reverseKGroup(cur-next, cur-next, 1); // 得到下一部分的新头以连接它ListNode* newhead __reverseKGroup(head_next , head, 1); // 得到这部分的新头并连接下部分的新头return newhead; // 返回这部分的新头给前一部分}return _reverseKGroup(cur-next, head, k1);}
public:ListNode* reverseKGroup(ListNode* head, int k) {K k;return _reverseKGroup(head, head,1);}
private:int K;
};
