(链表) 25. K 个一组翻转链表 ——【Leetcode每日一题】

❓ 25. K 个一组翻转链表

难度：困难

给你链表的头节点 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]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

进阶：你可以设计一个只用 $O(1)$ 额外内存空间的算法解决此问题吗？

💡思路：

本题的目标非常清晰易懂，不涉及复杂的算法，但是实现过程中需要考虑的细节比较多。

1. 先统计该链表中一共多少个节点 cnt，从而可以计算出一共要反转 cnt/k 个子链表，从而可以不用太关注边界；
2. 定义一个空的头节点，可以统一处理；
3. 定义两个指针 l 和 r ，分别指向已翻转链表的头和尾，每翻转 k 个节点，再重新计数。

🍁代码：(C++、Java)

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) {if(k == 1) return head;int cnt = 0;ListNode* p = head;while(p != nullptr){cnt++;p = p->next;}p = new ListNode(0, head);head = p;ListNode* l = p->next;ListNode* r = l;for(int i = 0; i < cnt / k; i++){int j = 1;while(j++ < k){p->next = r->next->next;r->next->next = l;l = r->next;r->next = p->next;p->next = l;}p = r;r = r->next;l = r;}return head->next;}
};

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {if(k == 1) return head;int cnt = 0;ListNode p = head;while(p != null){cnt++;p = p.next;}p = new ListNode(0, head);head = p;ListNode l = p.next;ListNode r = l;for(int i = 0; i < cnt / k; i++){int j = 1;while(j++ < k){p.next = r.next.next;r.next.next = l;l = r.next;r.next = p.next;p.next = l;}p = r;r = r.next;l = r;}return head.next;}
}

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n)$，其中 n 为链表的长度。
• 空间复杂度：$O(1)$，我们只需要建立常数个变量。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！

注： 如有不足，欢迎指正！