题目描述

题目链接

https://leetcode.cn/problems/reverse-nodes-in-k-group/

思路

本题的目标非常清晰易懂，不涉及复杂的算法，但是实现过程中需要考虑的细节比较多，容易写出冗长的代码。主要考查面试者设计的能力。

我们需要把链表节点按照个一组分组，所以可以使用一个指针依次指向每组的头节点。这个指针每次向前移动步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于。若是，我们就翻转这部分链表，否则不需要翻转。

接下来的问题就是「如何翻转一个分组内的子链表」。翻转一个链表并不难，具体过程如下：

具体代码如下：

public ListNode overturn(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode tmp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

但是对于一个子链表来说，除了翻转其本身之外，还需要记录子链表的前驱和后继节点，方便子链表翻转完成后把已翻转部分和未翻转部分通过翻转后的子链表连接起来。具体过程如下图所示：

代码实现

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0, head);
    ListNode pre = dummy;
    ListNode end = dummy;
    while (end.next != null) {
        // end为子链表的尾节点
        for (int i = 0; i < k && end != null; i++) {
            end = end.next;
        }
        // 如果待翻转的链表节点数小于k，不执行翻转
        if (end == null) {
            break;
        }
        // start为子链表的头节点
        ListNode start = pre.next;
        // next为下一个子链表的头节点
        ListNode next = end.next;
        // 翻转 start -> end
        end.next = null;
        pre.next = overturn(start);
        // 翻转后start为子链表的尾节点
        start.next = next;
        pre = start;
        end = pre;
    }
    return dummy.next;
}

复杂度分析

• 时间复杂度：，其中为链表的长度。指针会在个节点上停留，每次停留需要进行一次的翻转操作。
• 空间复杂度：，我们只需要建立常数个变量。