Hot 100 --- K 个一组翻转链表

本文概览：本文以LeetCode经典题目"K 个一组翻转链表"为例，从普通反转链表入手，重点讲解如何按组截取、如何保证前后链表不断开，以及如何用 NPC 三指针法完成局部链表反转

一、题目

二、题目分析

给定链表的头节点head，每k个节点一组进行翻转，返回修改后的链表。如果节点总数不是k的整数倍，最后剩余不足k个节点保持原有顺序

目标：每次翻转链表中的一小段，并保证整条链表不断开

核心难点：这题不是单纯反转整条链表，而是反转链表中的某一段。每反转一组之后，还要把这一组重新接回前后链表中

主要难点有两个：

  1. 如何反转当前这 k 个节点？
  2. 部分反转后，如何保证前面的链表和后面的链表不丢失？

思路概览

Java实现代码如下

public ListNode reverseKGroup(ListNode head, int k) { if (head == null || k <= 1) { return head; } // 创建哑节点 ListNode dummy = new ListNode(0, head); // 上一组的尾节点（初始为dummy） ListNode prevGroupEnd = dummy; while (true) { // 检查是否有足够的k个节点 ListNode groupEnd = prevGroupEnd; for (int i = 0; i < k; i++) { groupEnd = groupEnd.next; if (groupEnd == null) { return dummy.next; } } // 记录下一组的头节点（当前组的尾节点的下一个节点） ListNode nextGroupHead = groupEnd.next; // 记录当前组的头节点 ListNode curGroupHead = prevGroupEnd.next; // 反转链表之后返回新的头节点，将上一组的尾节点指向新的头节点 prevGroupEnd.next = reverse(curGroupHead, nextGroupHead); // 将上一组的尾节点更新为当前组的头节点（当前组反转后的尾节点） prevGroupEnd = curGroupHead; } } private ListNode reverse(ListNode curGroupHead, ListNode groupEnd) { // 记录当前反转后的组的最左节点 ListNode prev = groupEnd; // 记录当前组准备要反转的节点 ListNode curr = curGroupHead; // 准备反转的节点不等于组的尾节点，就说明还有节点没插完 while (curr != groupEnd) { ListNode nxt = curr.next; // ① 提前存住下一个要处理的节点 curr.next = prev; // ② 头插：当前节点挂到前面 prev = curr; // ③ 更新最左节点：当前节点成为新的最左节点 curr = nxt; // ④ 更新当前节点：处理下一个节点 } return prev; // 最左节点就是新的头节点：返回新的头节点 }

思路简要说明

  1. 按组处理：每次先检查后面是否还有 k 个节点，不足 k 个就直接结束

  2. 记录前后连接点：prevGroupEnd记录上一组的尾节点，nextGroupHead记录下一组的头节点，防止链表断开

  3. 局部反转：对[curGroupHead, nextGroupHead)这段链表进行反转，反转后返回新的头节点

  4. 接回链表：上一组尾节点连接到当前组反转后的新头节点，当前组原头节点变成新尾节点，作为下一轮的prevGroupEnd

三、思路详解

从普通反转链表入手

前面做过反转链表以后，这题的核心并不陌生。普通反转链表就是把整条链表从：

1 → 2 → 3 → 4

变成：

4 → 3 → 2 → 1

而这道题只是把"整条链表反转"变成了"每 k 个节点反转一次"：

原链表：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 k = 3 结果： 3 → 2 → 1 → 6 → 5 → 4 → 7 → 8

也就是说，我们每次只反转一小段链表，不足 k 个节点的部分保持不变

这题真正难在哪里？

思路本身不难：每次找到 k 个节点，然后反转它们

真正难的是代码实现，因为局部反转会带来两个问题：

问题一：当前组反转后，前面的链表怎么接回来？

比如：

dummy → 1 → 2 → 3 → 4 → 5

如果要反转1 → 2 → 3，反转后应该变成：

dummy → 3 → 2 → 1 → 4 → 5

这意味着上一组的尾节点dummy必须指向当前组反转后的新头节点 3

所以我们需要prevGroupEnd记录上一组的尾节点

问题二：当前组反转后，后面的链表不能丢失

反转1 → 2 → 3时，后面的4 → 5必须保留下来，并且反转后要接到 1 后面：

3 → 2 → 1 → 4 → 5

所以我们需要提前记录下一组的头节点nextGroupHead，也就是当前组尾节点的下一个节点

每一组需要记录哪些指针？

每次处理一组时，我们需要几个关键指针：

  • prevGroupEnd：上一组的尾节点，用来连接当前组反转后的新头节点
  • groupEnd：当前组的尾节点，用来判断是否有 k 个节点
  • nextGroupHead：下一组的头节点，也就是当前组反转时的终止位置
  • curGroupHead：当前组的头节点，反转后会变成当前组的尾节点

图示如下：

prevGroupEnd ↓ dummy → 1 → 2 → 3 → 4 → 5 → 6 ↑ ↑ ↑ curGroupHead groupEnd nextGroupHead 当前要反转的范围是：[curGroupHead, nextGroupHead) 也就是：1 → 2 → 3

为什么反转范围写成[curGroupHead, nextGroupHead)？

因为nextGroupHead是下一组的头节点，它不能被反转，只是作为当前组反转的终止边界

如何检查是否还有 k 个节点？

每一轮开始时，先让groupEnd从prevGroupEnd出发向后走 k 步：

ListNode groupEnd = prevGroupEnd; for (int i = 0; i < k; i++) { groupEnd = groupEnd.next; if (groupEnd == null) { return dummy.next; } }

如果走不到 k 步，说明剩余节点不足 k 个，直接返回结果。因为题目要求不足 k 个节点保持原顺序

NPC 三指针反转法

这里的reverse方法使用的是 NPC 三指针法：

  • nxt：next，提前保存当前节点的下一个节点，防止断链
  • prev：pre，已经反转部分的头节点
  • curr：cur，当前准备反转的节点

代码如下：

private ListNode reverse(ListNode curGroupHead, ListNode groupEnd) { ListNode prev = groupEnd; ListNode curr = curGroupHead; while (curr != groupEnd) { ListNode nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; } return prev; }

注意这里的prev初始值不是null，而是groupEnd（也就是下一组的头节点）

为什么？因为我们不是反转整条链表，而是反转某一段链表。当前组反转后，原来的头节点会变成当前组的尾节点，它的next应该指向下一组的头节点

所以一开始让：

ListNode prev = groupEnd;

这样反转过程中，当前组的尾部会天然接到下一组的头节点，不会断链

图示理解局部反转过程

以当前组1 → 2 → 3，下一组头节点为4为例：

反转前： prevGroupEnd → 1 → 2 → 3 → 4 → 5 ↑ ↑ curGroupHead groupEnd参数（这里实际是nextGroupHead=4） reverse(1, 4)

初始化：

prev = 4 curr = 1 4 → 5 ↑ prev 1 → 2 → 3 → 4 → 5 ↑ curr

第1轮：处理节点 1

nxt = curr.next; // nxt = 2 curr.next = prev; // 1 → 4 prev = curr; // prev = 1 curr = nxt; // curr = 2

结果：

1 → 4 → 5 ↑ prev 2 → 3 → 4 → 5 ↑ curr

此时节点 1 已经变成反转后这组的尾节点，并且自然接上了下一组的头节点 4

第2轮：处理节点 2

nxt = curr.next; // nxt = 3 curr.next = prev; // 2 → 1 prev = curr; // prev = 2 curr = nxt; // curr = 3

结果：

2 → 1 → 4 → 5 ↑ prev 3 → 4 → 5 ↑ curr

第3轮：处理节点 3

nxt = curr.next; // nxt = 4 curr.next = prev; // 3 → 2 prev = curr; // prev = 3 curr = nxt; // curr = 4

结果：

3 → 2 → 1 → 4 → 5 ↑ prev curr = 4，循环结束

此时prev就是当前组反转后的新头节点 3，返回prev

反转后如何接回上一组？

reverse(curGroupHead, nextGroupHead)返回的是当前组反转后的新头节点

所以：

prevGroupEnd.next = reverse(curGroupHead, nextGroupHead);

例如当前组1 → 2 → 3反转后变成3 → 2 → 1 → 4，返回的就是 3，于是：

dummy → 3 → 2 → 1 → 4 → 5

反转完成后，原来的当前组头节点curGroupHead已经变成了当前组的尾节点，所以要更新：

prevGroupEnd = curGroupHead;

这样下一轮反转时，prevGroupEnd就指向上一组的尾节点了

完整例子

以1 → 2 → 3 → 4 → 5 → 6 → 7 → 8，k = 3为例

第一组：1,2,3

反转前：dummy → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 反转后：dummy → 3 → 2 → 1 → 4 → 5 → 6 → 7 → 8 prevGroupEnd 更新为 1

第二组：4,5,6

反转前：dummy → 3 → 2 → 1 → 4 → 5 → 6 → 7 → 8 反转后：dummy → 3 → 2 → 1 → 6 → 5 → 4 → 7 → 8 prevGroupEnd 更新为 4

剩余：7,8 不足 3 个

不足 k 个，保持不变 最终结果：3 → 2 → 1 → 6 → 5 → 4 → 7 → 8
  • 时间复杂度：O(n)，每个节点只被处理一次
  • 空间复杂度：O(1)，只使用常数个指针变量