0025.K 个一组翻转链表

张开发
• 2026/4/15 6:01:17 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

0025.K 个一组翻转链表
题目链接https://leetcode.cn/problems/reverse-nodes-in-k-group/题目描述给定一个链表 head将链表每 k 个节点一组进行翻转并返回翻转后的链表。k 是正整数且小于或等于链表的长度。如果节点总数不是 k 的倍数则最后剩余的节点保持原样。解题思路先统计链表长度 n用于判断还有没有完整的 k 组可翻转。使用哑节点 dummy指针 p0 指向每一组要翻转的前驱节点方便翻转后拼接。对于每一组长度为 k 的区间采用原地头插式反转pre 作为局部反转的前驱上一节点cur 为当前遍历节点。连续执行 k 次“反转一步”操作将该组反转完成。反转完成后进行拼接原组头 p0.next 变为该组的尾需要接向 cur下一组的起点p0.next 指向 pre该组反转后的新头p0 前移到该组的尾部准备下一组。若剩余节点不足 k 个不再反转直接结束。题解代码classSolution{publicListNodereverseKGroup(ListNodehead,intk){// 1) 统计长度intn0;for(ListNodecurhead;cur!null;curcur.next){n;}// 2) 设置哑节点与工作指针ListNodedummynewListNode(0,head);ListNodep0dummy;// 指向每组反转前的前驱ListNodeprenull;// 反转时使用ListNodecurhead;// 当前节点// 3) 逐组反转for(;nk;n-k){// 反转当前这 k 个节点prenull;ListNodestartcur;// 记录当前组原始头反转后会变为尾for(inti0;ik;i){ListNodenxtcur.next;cur.nextpre;precur;curnxt;}// 4) 连接当前组与后续p0.nextpre;// 新头start.nextcur;// 组尾接向下一段p0start;// p0 前移到当前组尾准备下一组}returndummy.next;}}复杂度分析时间复杂度O(n)每个节点被访问和指针重连常数次。空间复杂度O(1)仅使用常数个辅助指针。

更多文章