题目链接

题目介绍

给你一个链表，每 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]

解题思路

创建节点hair
将hair节点的下一个节点指向head
定义节点cachePre，将cachePre指向hair。用来缓存子链表的上一个节点
循环当head不等于null时
- 定义尾节点tail，将tail指向cachePre （如果tail指向head的话，移动k个位置时，就有了K+1个节点
- 循环k次（主要意思为判断子链表的长度是否大于等于k）
  - 将tail往后移动
  - 判断tail是否为空，若为空，为数组元素个数小于k个，不需要反转，直接返回hair.next
- 定义节点cacheNext缓存子链表的下一个节点
- 反转子链表（单独函数，返回值要是数组，包括头节点和尾节点）
- 重新组织头节点和尾节点（head=反转后的头节点；tail=反转后的尾节点）
- 使用缓存的cachePre和cacheNext把子链表重新接回原链表
- 准备开始下一个子链表，将cachePre，head依次往后移动到当前的tail和tail.next处
返回值，hair.next

�
链表面试专题总结

:::tips 📌 有个小坑
本来思路还算清晰，结果这一行给整懵逼了，绕了好久

官方在反转单链表方法myReverse中定义了ListNode prev = tail.next;这句话其实会让人误解，闹不懂啥意思。如果这样写，翻转过后其实已经和下一段的头完成连接了，出来后只需要补上和上一段尾部的连接就好了
也可以写成ListNode prev = null;这样的话，在外面需要补上【上一段尾部的连接和下一段头部的链接】

区别见17行，如果定义了ListNode prev = tail.next;的话，就不需要缓存下一段的头节点
区别见23行，如果定义了ListNode prev = tail.next;的话，就不需要链接下一段的头节点
区别见33行，是否定义ListNode prev = tail.next;还是ListNode prev = null;

第2中写法，思路较清晰 :::

代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0);//因为头节点前面没有pre，所以创建节点
        hair.next = head;//将创建的节点与head连接
        ListNode pre = hair;//缓存子链表的上一个节点pre
        while (head != null) {
            ListNode tail = pre;//tail为子链表的尾节点
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;//移动K个，移动到子链表的末尾。
                if (tail == null) {
                    return hair.next;
                }
            }
            //当前链表长度为head --> tail
            ListNode[] reverse = myReverse(head, tail);//反转单链表
            head = reverse[0];//head为子链表的头节点
            tail = reverse[1];//tail为子链表的尾节点
            // 把子链表重新接回原链表
            pre.next = head;
            //开始下一个子链表。将pre，head依次往后移动
            pre = tail;
            head = tail.next;
        }
        return hair.next;
    }
    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return new ListNode[]{tail, head};
    }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0);//因为头节点前面没有pre，所以创建节点
        hair.next = head;//将创建的节点与head连接
        ListNode pre = hair;//缓存子链表的上一个节点pre
        while (head != null) {
            ListNode tail = pre;//tail为子链表的尾节点
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;//移动K个，移动到子链表的末尾。
                if (tail == null) {
                    return hair.next;
                }
            }
            //当前链表长度为head --> tail
            ListNode nex = tail.next;//缓存子链表的下一个节点
            ListNode[] reverse = myReverse(head, tail);//反转单链表
            head = reverse[0];//head为子链表的头节点
            tail = reverse[1];//tail为子链表的尾节点
            // 把子链表重新接回原链表
            pre.next = head;
            tail.next = nex;
            //开始下一个子链表。将pre，head依次往后移动
            pre = tail;
            head = tail.next;
        }
        return hair.next;
    }
    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = null;
        ListNode cur = head;
        while (prev != tail) {
            ListNode nex = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nex;
        }
        return new ListNode[]{tail, head};
    }
}

刷题记录 || 📝

25-K个一组翻转链表

题目链接

题目介绍

解题思路

代码