LeetCode 25. K 个一组翻转链表

约 5 分钟
文章信息 27 个分类 3 个标签
分类
LeetCode CodeTop 困难 已解决 需加强 500+ 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 拼多多 网易 小米 商汤 旷视 虾皮 哔哩哔哩 小红书 陌陌 LeetCode 热题 100 面试经典 150 题
标签
链表 递归 链表经典题
目录

题目描述

✅ 25. K 个一组翻转链表

image-20230226203302743

image-20230226203309669

题意分析

给定链表头节点 head 和整数 k，把链表每 k 个节点一组做反转；末尾不足 k 个的那一组保持原顺序。要求原地改指针，不能只交换节点值。

本题的算法内核就是 206 题的三指针反转，难点全在边界与拼接上，可以拆成三个必须回答的问题。

第一，反转前怎么确认这一组是完整的。因为不足 k 个不能动，所以必须先探明剩余节点数够不够，探明之后才能开始改指针——一旦改了指针再发现数量不够，就得再反转回去。

第二，反转后怎么把三段接起来。一组反转后，原来的组头变成组尾、原来的第 k 个节点变成组头。于是「上一组的尾」要指向新组头，「新组尾」要指向下一组的起点。漏掉任何一条都会断链或成环。

第三，第一组反转后整个链表的头变了。所以要用哨兵节点 dummy 挂在 head 前面，让「上一组的尾」这个角色在第一轮也有实体可用，最后返回 dummy.next。这是链表题中「头节点可能改变」的通用应对手法。

边界：k = 1 时相当于不做任何反转，答案是原链表；链表长度小于 k 时整条都不动；链表长度恰是 k 的倍数时最后一组也要反转，不存在保留段。

解法：分组迭代反转

核心思路

用虚拟头节点统一处理首组。每轮先找到本组第 k 个节点；不足 k 个直接结束，否则反转区间 [groupHead, groupNext)，再连接前后链表。

解题步骤

  • groupPrev 指向当前组的前一个节点。
  • 从 groupPrev 向后走 k 步找到 kth；找不到就返回。
  • 记录 groupNext = kth.next，以它作为反转终点。
  • 反转当前组，连接新组头和上一组尾。
  • 将旧组头作为新的 groupPrev，继续下一组。

代码实现

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;

        while (true) {
            ListNode kth = groupPrev;
            for (int i = 0; i < k && kth != null; i++) {
                kth = kth.next;
            }
            if (kth == null) {
                return dummy.next;
            }

            ListNode groupNext = kth.next;
            ListNode prev = groupNext;
            ListNode curr = groupPrev.next;
            while (curr != groupNext) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }

            ListNode oldHead = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = oldHead;
        }
    }
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Next: head}
    groupPrev := dummy

    for {
        kth := groupPrev
        for i := 0; i < k && kth != nil; i++ {
            kth = kth.Next
        }
        if kth == nil {
            return dummy.Next
        }

        groupNext := kth.Next
        prev, curr := groupNext, groupPrev.Next
        for curr != groupNext {
            next := curr.Next
            curr.Next = prev
            prev, curr = curr, next
        }

        oldHead := groupPrev.Next
        groupPrev.Next = kth
        groupPrev = oldHead
    }
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点至多参与一次定位和一次反转。
  • 空间复杂度：$O(1)$。

关键点总结

  • 先确认满 k 个节点，再修改指针。
  • 令 prev = groupNext，反转后组尾会自动接回后续链表。
  • 旧组头反转后变成组尾，也是下一轮的 groupPrev。

易错点总结

  • 不足 k 个仍然反转，违反题意。
  • 反转时写成 curr != kth，会漏掉第 k 个节点。
  • 重连后忘记更新 groupPrev，会重复处理同一组。

相似题目

题目 难度 考察点
206. 反转链表 简单 本题每组内部用的就是它的三指针骨架，必须先完全掌握
24. 两两交换链表中的节点 中等 k = 2 的特例，可直接套本题解法，也可写更简的三指针交换
92. 反转链表 II 中等 只反转一个指定区间，同样靠哨兵定位前驱并补两条连接
143. 重排链表 中等 找中点 + 反转后半段 + 交替合并，本题技巧是其中一环
234. 回文链表 简单 反转后半段再比对，练习区间反转与还原
61. 旋转链表 中等 同样需要先测长度、再定位断点、再重接，边界处理思路相通
LCR 024. 反转链表 简单 与 206 同题
LCR 026. 重排链表 中等 与 143 同题
LCR 027. 回文链表 简单 与 234 同题
剑指 Offer 24. 反转链表 简单 与 206 同题
面试题 02.06. 回文链表 简单 与 234 同题
补充题 18. 反转双向链表 中等 双向链表要同时翻转两个方向的指针，头尾也要互换