给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
image.png
image.png
就拿示例2来分析：
1.先把整个链表拆解成两份：
image.png
第一组是满足k（k=3）个节点的，可以进行翻转。
第二组无法满足k（k=3）个节点，不可进行翻转。
眼前的问题就是如何判断分解后的各组链表是否满足翻转条件？
最简单直接的办法就是遍历链表。
- 条件1:满足翻转条件的链表只需要遍历k次就结束遍历
- 条件2:不满足条件的链表next节点为null，导致无法达到k次遍历
ListNode next = head;
// 统计遍历的节点数量，用来检测是否满足k个节点的要求
int count = 0;
// 循环遍历链表，直至满足k个阶段，或者next指针为null就结束遍历
while (count < k && next != null){
next = next.next;
count++;
}
// 如果满足要求，就执行翻转
if (count == k){
// 执行翻转 TODO
} else {
// 不满足要求，那么返回链表本身，不需要翻转
return head;
}
2.链表翻转
image.png
- 翻转前，需要提前把下一个节点暂存起来，这样才能遍历下去，所以需要准备好ListNode next变量。
- 另外还需要准备ListNode prev，这个是用来作为翻转指针的指向目标
// 保留原来的head指针，创建一个临时指针来翻转。不改变head指向。
ListNode current = head;
ListNode next = null;
ListNode prev = null;
while (循环条件) {
// 暂存next节点。对应上图第一阶段
next = current.next;
// 反转current节点的next指针。对应上图第二阶段
current.next = prev;
// 翻转后处理，移动prev、current指针。对应上图第三阶段
prev = current;
current = next;
}
如此往复循环，直至翻转的次数达到k次，或者current节点为null，那么就结束循环
循环条件：
- 翻转次数达到k次
- current节点为null
ListNode current = head;
ListNode next = null;
ListNode prev = null;
int count = 0;
while (count < k && current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}
3.翻转完毕后，会存在以下两种情况
image.png
-
next不为null的话，那么就需要把next指向的链表再次执行翻转。
image.png
- next为null，后续不需要做任何处理，直接返回prev节点
if (next !=null){
head.next = k个节点链表翻转
}
return prev;
最终代码：
public ListNode reverseKGroup(ListNode head, int k){
// 首先，判断链表是否满足k个节点
// 需要遍历链表
ListNode next = head;
int count = 0;
// 遍历链表，统计数量
while (count < k && next != null){
next = next.next;
count++;
}
// 检查是否是否满足k
if (count == k){
// 执行翻转操作
ListNode prev = null;
next = null;
// 临时指针
ListNode current = head;
// 计算翻转次数
count = 0;
while (count < k && current != null){
// 暂存next节点
next = current.next;
// 翻转指向
current.next = prev;
// 翻转后指针向后移动
prev = current;
current = next;
}
if (next != null){
// 如果翻转后next不为null，说明后面的链表同样需要翻转
head.next = reverseKGroup(next, k);
}
// 返回翻转后的链表头节点
return prev;
} else {
// 不满足k个节点，直接返回原链表head
return head;
}
}
网友评论