一、题目描述
来源：力扣（LeetCode）
给你一个链表，每 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]
示例 3：
输入： head = [1,2,3,4,5], k = 1
输出： [1,2,3,4,5]
示例 4：
输入： head = [1], k = 1
输出： [1]
提示：
- 列表中节点的数量在范围
sz内 1 <= sz <= 50000 <= Node.val <= 10001 <= k <= sz
二丶思路分析
这道题也是对链表的反转，但是处理上要稍微复杂一些
- 首先我们要把一个链表 按照长度为 k 分成多个子链表，不足k时保持不变
- 然后依次将每个子链表，依次进行反转
- 每次反转后，将链表链接起来。即为最后结果
三、代码实现
/** * 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 (head == null || head.next == null || k ==1) { return head; } ListNode dummy = new ListNode(); dummy.next = head; // 记录要反转的子链表 ListNode tail = head; ListNode start= dummy; while (tail != null) { // 记录是否到达k了 int cnt =0; while (cnt < k && tail != null) { tail = tail.next; cnt++; } // 不够K个时 不反转 if (cnt < k) { break; } // 下一个子链表的头 ListNode tmp =start.next; // 反转 reverse(start, tail); start= tmp; } return dummy.next; } public void reverse(ListNode head, ListNode tail) { if (head == tail || head.next == tail) { return; } ListNode p1 = head.next; ListNode p2 = head.next.next; while (p2 != null && p2 != tail) { ListNode tmp = p2.next; p2.next = p1; p1 = p2; p2 = tmp; } head.next.next = tail; head.next = p1; } }
复杂度分析
时间复杂度：
网络异常，图片无法展示
|
n
为链表的长度
空间复杂度：
网络异常，图片无法展示
|
运行结果
网络异常，图片无法展示
|
总结
这道题目的目标和实现的逻辑比较容易搞清楚，主要是是实现过程中需要考虑的细节。如分组后的子链表是否反转，反转后的子链表与原链表的链接等等。
解决问题有时候也不一定是思路难，同样在实现的过程中，我们同样也要注意其中存在的一些小细节
继续加油~~
