【每日算法】LeetCode 25. K 个一组翻转链表

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 25. K 个一组翻转链表

1. 题目描述

给你链表的头节点head，每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]

说明：

• 链表中的节点数目为n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

2. 问题分析

这道题的核心是链表操作，前端开发者经常处理类似结构：

• DOM树节点操作（如批量重新排序元素）
• 虚拟DOM的diff算法中节点位置调整
• 数据流处理中的分批操作
• 实现分页、轮播等组件时的节点管理

关键难点：

1. 需要精确控制指针的指向关系
2. 处理边界情况（不足k个的情况）
3. 保持翻转后的正确连接
4. 需要保存关键节点位置以便后续连接

3. 解题思路

3.1 递归法（清晰直观）

时间复杂度：O(n)，空间复杂度：O(n/k)（递归栈深度）

• 递归处理每k个节点
• 翻转当前k个节点后，递归处理后续部分
• 将翻转后的子链表连接起来

3.2 迭代法（最优解）

时间复杂度：O(n)，空间复杂度：O(1)

• 使用虚拟头节点简化操作
• 分组遍历并翻转每一组
• 维护关键指针：前驱节点、当前组头、当前组尾
• 处理不足k个的情况

最优解：迭代法，因为它在O(n)时间内解决问题，且只使用常数级额外空间。

4. 代码实现

4.1 递归实现

/** * 递归解法 * 时间复杂度：O(n)，空间复杂度：O(n/k)（递归调用栈） */constreverseKGroupRecursive=function(head,k){// 检查是否有k个节点可供翻转letcurr=head;letcount=0;// 检查剩余节点是否足够k个while(curr!==null&&count<k){curr=curr.next;count++;}// 如果不足k个，直接返回当前头节点if(count<k){returnhead;}// 翻转当前k个节点letprev=null;letcurrent=head;for(leti=0;i<k;i++){constnext=current.next;current.next=prev;prev=current;current=next;}// 递归处理后续部分，并将当前翻转后的尾节点连接到后续结果head.next=reverseKGroupRecursive(current,k);// prev现在是翻转后的新头节点returnprev;};

4.2 迭代实现（最优）

/** * 迭代解法（最优解） * 时间复杂度：O(n)，空间复杂度：O(1) */constreverseKGroup=function(head,k){// 创建虚拟头节点，简化边界处理constdummy=newListNode(0);dummy.next=head;// pre指向当前要翻转的链表的前一个节点letpre=dummy;while(head){// tail指向当前要翻转的链表的尾部lettail=pre;// 查看剩余部分长度是否大于等于kfor(leti=0;i<k;i++){tail=tail.next;if(!tail){// 不足k个，直接返回结果returndummy.next;}}// next指向下一个要翻转的链表头constnextGroup=tail.next;// 翻转当前k个节点，返回翻转后的头尾节点const[newHead,newTail]=reverseList(head,tail);// 把翻转后的子链表重新接回原链表pre.next=newHead;newTail.next=nextGroup;// 更新pre和head，准备下一轮翻转pre=newTail;head=nextGroup;}returndummy.next;};/** * 辅助函数：翻转从head到tail的链表 * 返回翻转后的新头节点和新尾节点 */constreverseList=function(head,tail){letprev=tail.next;// 关键：连接到下一组的头letcurr=head;while(prev!==tail){constnext=curr.next;curr.next=prev;prev=curr;curr=next;}// 翻转后，tail成为新头，head成为新尾return[tail,head];};

4.3 可读性更好的迭代实现（适合前端理解）

/** * 更易理解的迭代解法 * 将翻转逻辑拆解为更小的函数 */constreverseKGroupEasy=function(head,k){// 计算链表长度constgetLength=(node)=>{letlen=0;while(node){len++;node=node.next;}returnlen;};// 翻转链表的一部分constreversePart=(start,end)=>{letprev=end.next;// 连接到下一组的头letcurr=start;while(prev!==end){constnext=curr.next;curr.next=prev;prev=curr;curr=next;}return[end,start];// 返回新头和新尾};constlength=getLength(head);constdummy=newListNode(0);dummy.next=head;letprev=dummy;// 计算可以翻转多少组constgroups=Math.floor(length/k);for(leti=0;i<groups;i++){// 定位当前组的头和尾letgroupHead=prev.next;letgroupTail=prev;for(letj=0;j<k;j++){groupTail=groupTail.next;}// 下一组的头constnextGroup=groupTail.next;// 翻转当前组const[newHead,newTail]=reversePart(groupHead,groupTail);// 重新连接prev.next=newHead;newTail.next=nextGroup;// 更新prev，准备下一组prev=newTail;}returndummy.next;};

5. 复杂度对比分析

性能总结：

• 迭代法是最优选择，尤其对于大规模数据
• 递归法在k值较小时表现良好，代码更简洁