给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
解题思路
将整个链表分为三部分 前驱部分 -> 要翻转的部分 -> 后继部分
先解决如何翻转给定的一个链表
- 定义pre指向null, cur指向head, next指向null
- 当cur不为空时循环
- next 指向cur.next, 保存当前节点后面的链表
- cur.next 指向pre
- pre 指针向后移动, pre 指向 cur
- cur 指针向后移动, cur 指向 next
- 返回 pre
然后解决如何在给定链表中逐k个翻转
- 定义辅助节点 temp, 并将 temp.next 指向 head
- 再定义 pre 指向 temp
- 然后从 pre 开始往后数 k 次找到要翻转的链表的尾节点
- 记录该尾节点的后继为 next, 然后将尾节点的 next 置为 null 以断开链表
- 然后定义 start 指向 pre.next, start 为要翻转的链表的头节点
- 有了 start 就可以用上面的方法翻转给定那段链表
-
pre.next = reverse(start)将 pre 与翻转后的链表接上 - 翻转后 start 成了那段链表的尾节点, 于是
start.next = next便把那段链表的尾部也重新接回原链表 - 然后更新各个指针
end = start; pre = start, 重复翻转操作
代码
class Solution {
// 链表翻转 head: 1->2->3->4
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
ListNode next;
while (cur != null) {
next = cur.next; // next 指向下一个节点, 保存当前节点后面的链表
cur.next = pre; // 将当前节点 next 指向前一个节点 null<-1<-2<-3<-4
pre = cur; // pre 指针向后移动, pre 指向当前节点
cur = next; // cur 指针向后移动, cur指向下一个节点
}
return pre;
}
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
// 定义辅助节点保存最终头节点的上一个节点
ListNode temp = new ListNode();
// pre指向每次要交换的那段链表的前一个节点
ListNode pre = temp;
// 注意将pre指向头节点
pre.next = head;
// start指向每次要交换的那段链表的第一个节点
ListNode start = pre;
// end指向每次要交换的那段链表的尾节点
ListNode end = start;
// next指向每次要交换的那段链表的后继节点
ListNode next;
while (end.next != null) {
// 通过循环找到要翻转的那段链表的最后节点
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
// 注意: 遍历的时候如果end为null, 则说明剩余链表不足k个
if (end == null) {
break;
}
// 记录要翻转的那段链表的尾节点的下一个节点
next = end.next;
// 断开链表
end.next = null;
// start指向前驱节点的下一个
start = pre.next;
// 反转
// 前驱的next指向反转后的那段链表的头
pre.next = reverse(start);
// 翻转后的start变为"翻转的那段链表"的尾节点, 将其next指向原来保存的next
start.next = next;
// 更新end, 下一轮要继续寻找下一段链表的尾节点
end = start;
// 此时的start也刚好是下一段要翻转的链表的前驱节点
pre = start;
}
return temp.next;
}
}
